Cod sursa(job #639009)

Utilizator ELHoriaHoria Cretescu ELHoria Data 22 noiembrie 2011 09:21:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <string>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


void kmp_match(const string &t,const string &p)
{	
	int q = 0 , match = 0 , v[1002];
	int n = (int)t.length() , m = (int)p.length();

	int *a = new int[m] , k = 0;
	a[0] = 0;
	for(int q = 1; q < m; q++)
	{
		while (k > 0 && p[k] != p[q])
			k = a[k-1];

		if (p[k] == p[q])
			k++;

		a[q] = k;
	}

	for (int i = 0; i < n; i++)
	{
		while(q > 0 && p[q] != t[i]) 
			q = a[q-1];

		if (p[q] == t[i]) 
			q++;

		if (q == m) 
		{
			if(match<1000) v[match] = i - m + 1;
			match++;
			q = a[q-1];
		}
	}
	fout<<match<<'\n';
	match = min(match,1000);
		for(int i=0;i<match;++i)
			fout<<v[i]<<" ";

}

int main()
{
	string A , B;
	fin>>A>>B;
	kmp_match(B,A);
	return 0;
}