Pagini recente » Cod sursa (job #2632675) | Cod sursa (job #1757566) | Cod sursa (job #957104) | Cod sursa (job #2491005) | Cod sursa (job #2063224)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char s[20000000],a[20000000];
int p[2000000],n,m,sol[1001];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ok=1;
void prefix()
{
int i=0;
for(int j=1;j<m;j++)
{
if(a[i]==a[j])
{
p[j]=1+p[j-1];
i++;
}
else
{
i=p[j-1];
if(a[i]==a[j])
{
p[i]=1;
i++;
}
}
}
}
void kmp()
{
int i=0,j=0;
while(i<n)
{
while(s[i]==a[j])
{
i++;j++;
if(j==m&&ok<=1000)
sol[ok]=i-m;
if(i>=n)
break;
}
j=p[j-1];
i++;
}
}
int main()
{
fin.getline(a,20000000);
fin.getline(s,20000000);
n=strlen(s);
m=strlen(a);
prefix();
kmp();
/*for(int i=0; i<m; i++)
cout<<p[i];*/
fout<<ok<<endl;
for(int i=1;i<=ok;i++)
fout<<sol[i]<<" ";
return 0;
}