Cod sursa(job #685656)

Utilizator ChallengeMurtaza Alexandru Challenge Data 21 februarie 2012 08:39:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2000111;

ifstream fin(InFile);
ofstream fout(OutFile);

int matches,P[MaxN];
char N[MaxN],M[MaxN];
vector<int> sol;

inline void prefix()
{
	int len=strlen(N+1);
	int k=0;
	P[1]=0;
	for(register int i=2;i<=len;++i)
	{
		while(k && N[i]!=N[k+1])
		{
			k=P[k];
		}
		if(N[i]==N[k+1])
		{
			++k;
		}
		P[i]=k;
	}
}

inline void kmp()
{
	int len2=strlen(N+1);
	int len=strlen(M+1);
	int k=0;
	for(register int i=1;i<=len;++i)
	{
		while(k && M[i]!=N[k+1])
		{
			k=P[k];
		}
		if(M[i]==N[k+1])
		{
			++k;
		}
		if(k==len2)
		{
			++matches;
			if(matches<=1000)
			{
				sol.push_back(i-len2);
			}
		}
	}
}

int main()
{
	fin>>N+1;
	fin>>M+1;
	fin.close();
	
	prefix();
	kmp();
	
	fout<<matches<<"\n";
	for(vector<int>::iterator it=sol.begin();it!=sol.end();++it)
	{
		fout<<*it<<" ";
	}
	fout.close();
	return 0;
}