Pagini recente » Cod sursa (job #548384) | Cod sursa (job #264171) | Cod sursa (job #456595) | Cod sursa (job #601115) | Cod sursa (job #1471929)
#include <fstream>
#include <cstring>
#define MAXN 2000001
#define MAXM 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Prefix[MAXM+3],sol[1001],nrsol;
char P[MAXM+1], T[MAXN+1];
void KMP_prefix(char P[],int Prefix[])
{
int a,b,length;
length=strlen(P);
Prefix[0]=-1;
Prefix[1]=0;
a=0;
for(b=2;b<=length;b++)
{
while(a>0 && P[a+1]!=P[b])
a=Prefix[a];
if(P[a+1]==P[b])
a=a+1;
Prefix[b]=a;
}
}
void KMP(char T[],char P[], int Prefix[])
{
int i,j,k,n,m;
i=0;j=0;k=0;
m=strlen(P) ;
n=strlen(T) ;
while(n-k+2 >= m)
{
while(j<m && T[i]==P[j]) { i++; j++; }
if(j>=m)
{
nrsol++;
sol[nrsol]=k-1;
}
if (nrsol>=1000)
break;
if(Prefix[j]>0)
k=i-Prefix[j]+1;
else
{
if(i==k)
i++;
k=i;
}
if(j>0)
j=Prefix[j]+1;
}
}
int main()
{
fin.getline(P,MAXM);
fin.getline(T,MAXN);
KMP_prefix(P,Prefix);
KMP(T,P,Prefix);
fout<<nrsol<<'\n';
int i;
for(i=1;i<=nrsol;i++)
fout<<sol[i]<<' ';
fout<<'\n';
return 0;
}