Cod sursa(job #570957)

Utilizator joRicelAvadanei Danut joRicel Data 3 aprilie 2011 19:58:25
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#define InF "strmatch.in"
#define OutF "strmatch.out"
#define LgMax 2000002
using namespace std;
ifstream fin(InF);
ofstream fout(OutF);
char W[LgMax],S[LgMax];
int T[LgMax],leng,leng_W,k,V[LgMax];
void make_pref();
void kmp();
int main()
{
	fin.getline(W,LgMax);
	fin.get();
	fin.getline(S,LgMax);
	leng = strlen(S);
	leng_W = strlen(W);
	make_pref();
	kmp();
	fout<<k<<"\n";
	for(int i = 0;i < k;i++)
		fout<<V[i] + 1<<" ";
	return 0;
}
void make_pref()
{
	int pos = 2, cnd = 0;
	T[0] = -1;T[1] = 0;
	while(pos < leng_W)
	{
		if(W[pos - 1] == W[cnd])
		{
			cnd++;
			T[pos] = cnd;
			pos++;
		}
		else if(cnd > 0)
			cnd = T[cnd];
		else
			T[pos] = 0, pos++;
	}
}
void kmp()
{
	int m = 0,i = 0,q;
	while(i + m < leng)
	{
		if(W[i] == S[m + i])
		{
			if(i == leng_W - 1)
			{
				V[k++] = m;
				m = m + i - T[i];
				if(T[i] > -1)
					i = T[i];
				else
					i = 0;
			}
            i++;
		}
        else
		{
            m = m + i - T[i];
            if(T[i] > -1)
                i = T[i];
            else
                i = 0;
		}
	}
	for (i = 1; i <= leng; ++i)
	{		
		while (q && S[q+1] != W[i])
			q = T[q];
		if (S[q+1] == W[i])
			++q;
		if (q == leng_W)
		{
			q = T[leng_W];
			++k;
			if (k <= 1000)
				T[k] = i-leng_W;	
		}	
	}		
}