Удалить самый большой повторяющийся фрагмент из списка

0

1

Проблема следующая. Имеется папка с файлами, проименованными в виде:

01 beneath the massacre symptoms.mp3
02 beneath the massacre hunted.mp3
03 beneath the massacre left hand.mp3
04 beneath the massacre hopes.mp3
05 beneath the massacre it.mp3
06 beneath the massacre light.mp3
07 beneath the massacre incongruous.mp3
08 beneath the massacre pedestal.mp3
09 beneath the massacre grief.mp3
10 beneath the massacre damages.mp3
11 beneath the massacre unheard.mp3

Я не хочу, чтобы самый большой фрагмент названия «beneath the massacre » мозолил глаза, и нужно его удалить. Я уже написал скрипт, который позволяет удалять ненужный фрагмент, однако в нем надо явно указывать этот фрагмент. А ситуация, когда появляется ненужный фрагмент, встречается часто, поэтому возникает следующий вопрос: как можно найти самый большой произвольный фрагмент автоматически, чтобы его можно было не указывать каждый раз?

Ссылка

←	Компиляция программ использующие LLVM на Windows

При пересборке Qt4 система ищет qmake в домашней директории

→

Если положение фрагмента фиксировано, то можно просто складывать: abc <+> ebc = " bc".

Например на python / ruby.

anonymous
(17.02.12 23:42:19 MSK)

Ответ на: комментарий от anonymous 17.02.12 23:42:19 MSK

Дайте, пожалуйста, простейший алгоритм (желательно, на bash). Я в программировании не силен.

Deleted
(17.02.12 23:44:27 MSK)

Ответ на: комментарий от Deleted 17.02.12 23:44:27 MSK

Можно так, правда, он секунду думает, из хаскеля инерпретатор пока хреновый.

eddie -m Data.List «foldr1 (zipWith $ \x y -> if x == y then x else ' ') . lines»

На баш влом (пишешь функцию, которая неодинаковые символы заменет на заполнитель: цикл по короткой строке, потом сию ф-ию применить на строки входа).

anonymous
(17.02.12 23:54:33 MSK)

Ссылка

[humor]

$ echo '01 beneath the massacre symptoms.mp3
02 beneath the massacre hunted.mp3
03 beneath the massacre left hand.mp3
04 beneath the massacre hopes.mp3
05 beneath the massacre it.mp3
06 beneath the massacre light.mp3
07 beneath the massacre incongruous.mp3
08 beneath the massacre pedestal.mp3
09 beneath the massacre grief.mp3
10 beneath the massacre damages.mp3
11 beneath the massacre unheard.mp3' | sed 's/.* //'

[/humor]

anTaRes ★★★★
(18.02.12 01:23:15 MSK)

Ссылка

Наибольшая общая подстрока.

#include <map>
#include <string>
#include <iostream>
#include <set>

int gcs (const std::set<std::string> &strings, std::set<std::string> *best_substr)
{
	typedef std::multimap<std::string, std::string::size_type> SubStrPool; // Ключ подстрока, значение - смещение подстроки в исходной строке.
	std::map<std::string, SubStrPool> substrings;

	int len=0;

	for (std::set<std::string>::const_iterator i=strings.begin(), e=strings.end(); i!=e; ++i)
	{
		const std::string &s(*i);
		SubStrPool &sp(substrings[s]);

		for (std::string::size_type i=0, e=s.size(); i<e; i++) {
			sp.insert (SubStrPool::value_type(std::string(1, s[i]), i));
			best_substr->insert(std::string(1, s[i]));
			len=1;
		}
	}

	do
	{
		std::set<std::string> current_substr;

		for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::string &s(i->first);
			SubStrPool &sp(i->second);

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(), x1; x!=e;) {
				const std::string &substr(x->first);
				bool found=true;

				for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); found && i!=e; ++i)
					if (&i->first!=&s)
						found=i->second.find (substr)!=i->second.end();

				if (!found) {
					x1=x;
					x1++;
					sp.erase (x);
					x=x1;
				} else {
					current_substr.insert (substr);
					x++;
				}
			}
		}

		if (current_substr.empty())
			return len;

		*best_substr=current_substr;

		for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::string &s(i->first);
			SubStrPool &sp(i->second), sp1;

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(); x!=e; x++) {
				const std::string &substr(x->first);
				std::string::size_type len=substr.length();
				if (x->second+len<s.length())
					sp1.insert (SubStrPool::value_type(s.substr(x->second, len+1), x->second));
			}
			sp=sp1;
		}

		len++;
	} while (true);

	return len;
}

int main()
{
	std::set<std::string> strings, gstrings;

	strings.insert ("01 beneath the massacre symptoms.mp3");
	strings.insert( "02 beneath the massacre hunted.mp3");
	strings.insert ("03 beneath the massacre left hand.mp3");
	strings.insert ("04 beneath the massacre hopes.mp3");
	strings.insert ("05 beneath the massacre it.mp3");
	strings.insert ("06 beneath the massacre light.mp3");
	strings.insert ("07 beneath the massacre incongruous.mp3");
	strings.insert ("08 beneath the massacre pedestal.mp3");
	strings.insert ("09 beneath the massacre grief.mp3");
	strings.insert ("10 beneath the massacre damages.mp3");
	strings.insert ("11 beneath the massacre unheard.mp3");

	gcs (strings, &gstrings);

	for (std::set<std::string>::iterator i=gstrings.begin(), e=gstrings.end(); i!=e; i++)
		std::cout << *i << "\n";
}

~/linux.org.ru/greatest-common-string$ ./gcs 
 beneath the massacre 
~/linux.org.ru/greatest-common-string$

loki231
(18.02.12 14:09:47 MSK)

Ответ на: Наибольшая общая подстрока. от loki231 18.02.12 14:09:47 MSK

Ух ты, сколько кода специально для меня написали, спасибо огромное. Но я все равно C не знаю, у меня не скомпилировалось, и еще ведь нужны не конкретно заданные строки, а чтение папки через find или ls.

Deleted
(18.02.12 22:44:50 MSK)

Ответ на: комментарий от Deleted 18.02.12 22:44:50 MSK

не написали с скопипастили :)

а по теме: можно взять VIM и сделать дело с помощью вертикального блочного выделения

q11q11 ★★★★★
(18.02.12 23:15:59 MSK)

Ссылка

Это же просто :)

S='01 beneath the massacre symptoms.mp3
02 beneath the massacre hunted.mp3
03 beneath the massacre left hand.mp3
04 beneath the massacre hopes.mp3
05 beneath the massacre it.mp3
06 beneath the massacre light.mp3
07 beneath the massacre incongruous.mp3
08 beneath the massacre pedestal.mp3
09 beneath the massacre grief.mp3
10 beneath the massacre damages.mp3
11 beneath the massacre unheard.mp3'

R=$(echo $S | sed -re 's:^[0-9]+::' | perl -e '$a=scalar <>;while(<>){$b=$_;for$i(0..length $a){for$j(1+$i..length $a){$s=substr($a,$i,$j);if(index($b,$s) != -1){$S = $s if length $s > length $S}}}}; END{print $S}')

echo $S | while read f; do echo "$f" '->' "$(echo "$f" | perl -npe "s#^.*\Q$R\E##")"; done

user_2190
(18.02.12 23:19:53 MSK)

Ответ на: комментарий от user_2190 18.02.12 23:19:53 MSK

Или с сохранением префикса:

echo $S | while read f; do echo "$f" '->' "$(echo "$f" | perl -npe "s#^(.*)\Q$R\E#\1 #")"; done

user_2190
(18.02.12 23:27:09 MSK)

Ответ на: комментарий от user_2190 18.02.12 23:27:09 MSK

Эх, поспешил я, вот в результате правильный вариант:

R=$(echo $S | sed -re 's:^[0-9]+::' | perl -e '$a=scalar <>;while(<>){$b=$_;for$i(0..length $a){for$j(1+$i..length $a){$s=substr($a,$i,$j);if(index($b,$s) != -1){$S = $s if length $s > length $S}}}$a=$S};END{print $S}')

echo $S | while read f; do echo "$f" '->' "$(echo "$f" | perl -npe "s#^(.*)\Q$R\E#\1 #")"; done

user_2190
(18.02.12 23:37:19 MSK)

Ссылка

Ответ на: комментарий от Deleted 18.02.12 22:44:50 MSK

Удаление наибольшей общей строки

Файл gcs.c

#include <cstring>
#include <map>
#include <string>
#include <iostream>
#include <set>
#include <list>

int gcs (const std::set<std::string> &strings, std::set<std::string> *best_substr)
{
	best_substr->clear();

	switch (strings.size()) {
	case 0:
		return 0;
	case 1: {
		const std::string &s(*strings.begin());
		best_substr->insert (s);
		return s.length();
	}
	}

	typedef std::multimap<std::string, std::string::size_type> SubStrPool; // Ключ подстрока, значение - смещение подстроки в исходной строке.
	std::map<std::string, SubStrPool> substrings;

	int len=0;

	for (std::set<std::string>::const_iterator i=strings.begin(), e=strings.end(); i!=e; ++i)
	{
		const std::string &s(*i);
		SubStrPool &sp(substrings[s]);

		for (std::string::size_type i=0, e=s.size(); i<e; i++) {
			sp.insert (SubStrPool::value_type(std::string(1, s[i]), i));
			best_substr->insert(std::string(1, s[i]));
			len=1;
		}
	}

	do
	{
		std::set<std::string> current_substr;

		for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::string &s(i->first);
			SubStrPool &sp(i->second);

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(), x1; x!=e;) {
				const std::string &substr(x->first);
				bool found=true;

				for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); found && i!=e; ++i)
					if (&i->first!=&s)
						found=i->second.find (substr)!=i->second.end();

				if (!found) {
					x1=x;
					x1++;
					sp.erase (x);
					x=x1;
				} else {
					current_substr.insert (substr);
					x++;
				}
			}
		}

		if (current_substr.empty())
			return len;

		*best_substr=current_substr;

		for (std::map<std::string, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::string &s(i->first);
			SubStrPool &sp(i->second), sp1;

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(); x!=e; x++) {
				const std::string &substr(x->first);
				std::string::size_type len=substr.length();
				if (x->second+len<s.length())
					sp1.insert (SubStrPool::value_type(s.substr(x->second, len+1), x->second));
			}
			sp=sp1;
		}

		len++;
	} while (true);

	return len;
}

int main()
{
	std::set<std::string> strings, gstrings;

	// strings.insert ("01 beneath the massacre symptoms.mp3");
	// strings.insert( "02 beneath the massacre hunted.mp3");
	// strings.insert ("03 beneath the massacre left hand.mp3");
	// strings.insert ("04 beneath the massacre hopes.mp3");
	// strings.insert ("05 beneath the massacre it.mp3");
	// strings.insert ("06 beneath the massacre light.mp3");
	// strings.insert ("07 beneath the massacre incongruous.mp3");
	// strings.insert ("08 beneath the massacre pedestal.mp3");
	// strings.insert ("09 beneath the massacre grief.mp3");
	// strings.insert ("10 beneath the massacre damages.mp3");
	// strings.insert ("11 beneath the massacre unheard.mp3");

	char buf[1024];

	std::list<std::string> src_strings;

	while (std::cin.getline (buf, sizeof buf))
	{
		std::string s(buf, strlen(buf));
		src_strings.push_back (s);
		strings.insert (s);
	}

	if (gcs (strings, &gstrings)>=4)
		for (std::list<std::string>::iterator i=src_strings.begin(); i!=src_strings.end(); i++)
			for (std::set<std::string>::iterator x=gstrings.begin(), e=gstrings.end(); x!=e; x++) {
				std::string::size_type pos=i->find (*x);
				if (pos!=std::string::npos)
					i->replace (pos, x->length(), " ");
			}

	for (std::list<std::string>::iterator i=src_strings.begin(); i!=src_strings.end(); i++)
		std::cout << *i << "\n";

	return 0;
}

Файл Makefile

gcs: gcs.c
	c++ -Wall -o $@ $<

Cкладываешь эти два файла в одну директорию и запускаешь make. Список строк на стандартный ввод, обработанный список - на стандартном выводе.Общая строка удаляется, если она не короче 4 символов.

loki231
(19.02.12 02:31:31 MSK)

Ссылка

Поиск и удаление наибольшей общей подстроки

Поведение предыдущих версий при работе с русскими буквами в многобайтных кодировках (вроде UTF-8) достойно всяческого порицания!

Вариант, приведённый ниже, корректно работает и такими кодировками.

Файл gcs.c


#include <map>
#include <string>
#include <iostream>
#include <set>
#include <list>

int gcs (const std::set<std::wstring> &strings, std::set<std::wstring> *best_substr)
{
	best_substr->clear();

	switch (strings.size()) {
	case 0:
		return 0;
	case 1: {
		const std::wstring &s(*strings.begin());
		best_substr->insert (s);
		return s.length();
	}
	}

	typedef std::multimap<std::wstring, std::wstring::size_type> SubStrPool; // Ключ подстрока, значение - смещение подстроки в исходной строке.
	std::map<std::wstring, SubStrPool> substrings;

	int len=0;

	for (std::set<std::wstring>::const_iterator i=strings.begin(), e=strings.end(); i!=e; ++i)
	{
		const std::wstring &s(*i);
		SubStrPool &sp(substrings[s]);

		for (std::wstring::size_type i=0, e=s.size(); i<e; i++) {
			sp.insert (SubStrPool::value_type(std::wstring(1, s[i]), i));
			best_substr->insert(std::wstring(1, s[i]));
			len=1;
		}
	}

	do
	{
		std::set<std::wstring> current_substr;

		for (std::map<std::wstring, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::wstring &s(i->first);
			SubStrPool &sp(i->second);

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(), x1; x!=e;) {
				const std::wstring &substr(x->first);
				bool found=true;

				for (std::map<std::wstring, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); found && i!=e; ++i)
					if (&i->first!=&s)
						found=i->second.find (substr)!=i->second.end();

				if (!found) {
					x1=x;
					x1++;
					sp.erase (x);
					x=x1;
				} else {
					current_substr.insert (substr);
					x++;
				}
			}
		}

		if (current_substr.empty())
			return len;

		*best_substr=current_substr;

		for (std::map<std::wstring, SubStrPool>::iterator i=substrings.begin(), e=substrings.end(); i!=e; ++i)
		{
			const std::wstring &s(i->first);
			SubStrPool &sp(i->second), sp1;

			for (SubStrPool::iterator x=sp.begin(), e=sp.end(); x!=e; x++) {
				const std::wstring &substr(x->first);
				std::wstring::size_type len=substr.length();
				if (x->second+len<s.length())
					sp1.insert (SubStrPool::value_type(s.substr(x->second, len+1), x->second));
			}
			sp=sp1;
		}

		len++;
	} while (true);

	return len;
}

int main()
{
	setlocale (LC_ALL, "");

	std::set<std::wstring> strings, gstrings;

	// strings.insert ("01 beneath the massacre symptoms.mp3");
	// strings.insert( "02 beneath the massacre hunted.mp3");
	// strings.insert ("03 beneath the massacre left hand.mp3");
	// strings.insert ("04 beneath the massacre hopes.mp3");
	// strings.insert ("05 beneath the massacre it.mp3");
	// strings.insert ("06 beneath the massacre light.mp3");
	// strings.insert ("07 beneath the massacre incongruous.mp3");
	// strings.insert ("08 beneath the massacre pedestal.mp3");
	// strings.insert ("09 beneath the massacre grief.mp3");
	// strings.insert ("10 beneath the massacre damages.mp3");
	// strings.insert ("11 beneath the massacre unheard.mp3");

	wchar_t buf[1024];

	std::list<std::wstring> src_strings;

	while (std::wcin.getline (buf, sizeof buf))
	{
		std::wstring s(buf, wcslen(buf));
		src_strings.push_back (s);
		strings.insert (s);
	}

	if (gcs (strings, &gstrings)>=4)
		for (std::list<std::wstring>::iterator i=src_strings.begin(); i!=src_strings.end(); i++)
			for (std::set<std::wstring>::iterator x=gstrings.begin(), e=gstrings.end(); x!=e; x++) {
				std::wstring::size_type pos=i->find (*x);
				if (pos!=std::wstring::npos)
					i->replace (pos, x->length(), pos? L" ": L"");
			}

	for (std::list<std::wstring>::iterator i=src_strings.begin(); i!=src_strings.end(); i++)
		std::wcout << *i << "\n";

	return 0;
}

Файл Makefile

gcs: gcs.c
	c++ -Wall -o $@ $<

loki231
(20.02.12 19:29:30 MSK)

Ссылка

Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.

←	Компиляция программ использующие LLVM на Windows

Development

При пересборке Qt4 система ищет qmake в домашней директории

→

Наибольшая общая подстрока.

Удаление наибольшей общей строки

Поиск и удаление наибольшей общей подстроки

Похожие темы