Cod sursa(job #570949)

Utilizator joRicelAvadanei Danut joRicel Data 3 aprilie 2011 19:52:21
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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;
	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;
		}
	}
}