Pagini recente » Cod sursa (job #3128046) | Cod sursa (job #173380) | Cod sursa (job #55331) | Cod sursa (job #633879) | Cod sursa (job #1586880)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000005],s2[2000005];
int len1,len2,pi[2000005],sol[1005],nsol;
void Prefix()
{ int i,k=0;
for(i=2;i<=len1;i++)
{
while(s1[k+1]!=s1[i] && k)
k=pi[k];
if (s1[k+1]==s1[i]) k++;
pi[i]=k;
}
}
void KMP()
{ int i,k=0;
for(i=1;i<=len2;i++)
{
while(s1[k+1]!=s2[i] && k)
k=pi[k];
if (s1[k+1]==s2[i]) k++;
if (k==len1)
{ nsol++;
if (nsol<=1000) sol[nsol]=i-k+1;
}
}
}
int main()
{ int i;
f>>s1+1>>s2+1;
len1=strlen(s1+1);
len2=strlen(s2+1);
Prefix();
KMP();
g<<nsol<<"\n";
for(i=1;i<=nsol;i++)
g<<sol[i]-1<<" ";
return 0;
}