Cod sursa(job #1446212)

Utilizator Rares95Rares Arnautu Rares95 Data 1 iunie 2015 02:22:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
# include <cstdio>
# include <string>
# include <iostream>
# include <cstring>
using namespace std;

# define max_size 2000000
# define max_matches 1000

class KMP
{
private:
	char Text[max_size];
	char Pattern[max_size];
	int Prefix[max_size];
	int matchesCount, matches[max_matches];
	int textLength, patternLength;

public:
	KMP(char text[], char pattern[])
	{
		for (int i = 0; i < max_size; ++i)
		{
			Text[i] = text[i];
			Pattern[i] = pattern[i];
		}
		textLength = strlen(Text) - 1;
		patternLength = strlen(Pattern) - 1;
	}

	void Compute_Prefix_function()
	{
		Prefix[1] = 0;
		int k = 0;
		for (int q = 2; q <= patternLength; ++q)
		{
			while (k > 0 && Pattern[k + 1] != Pattern[q])
				k = Prefix[k];
			if (Pattern[k + 1] == Pattern[q])
				++k;
			Prefix[q] = k;
		}
	}

	void KMP_Match()
	{
		Compute_Prefix_function();
		int q = 0;
		matchesCount = 0;
		for (int i = 1; i <= textLength; ++i)
		{
			while (q > 0 && Pattern[q + 1] != Text[i])
				q = Prefix[q];
			if (Pattern[q + 1] == Text[i])
				++q;
			if (q == patternLength)
			{
				matches[matchesCount++] = i - patternLength;
				if (matchesCount < max_matches)
					q = Prefix[q];
				else
					return;
			}
		}
	}

	void printSolution()
	{
		printf("%d\n", matchesCount);
		for (int i = 0; i < matchesCount; ++i)
			printf("%d ", matches[i]);
		printf("\n");
	}

};

char text[max_size], pattern[max_size];

int main()
{
	text[0] = pattern[0] = 'a';

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s %s", pattern + 1, text + 1);
	
	KMP *rez = new KMP(text, pattern);
	rez->KMP_Match();
	rez->printSolution();

	return 0;
}