Pagini recente » Cod sursa (job #886914) | Cod sursa (job #1404766) | Cod sursa (job #2853048) | Cod sursa (job #506006) | Cod sursa (job #1125126)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,p[2000005],v[2000005],ap;
char a[2000005],b[2000005];
void Prefix()
{ int k=0,i;
for(i=1;i<n;i++)
{
while(k>0 && a[k]!=a[i])
k=p[k-1];
if (a[k]==a[i])
{k++; p[i]=k;}
}
}
int main()
{ int i,k;
f.getline(a,2000003);
f.getline(b,2000003);
n=strlen(a);
m=strlen(b);
Prefix();
k=0;
for(i=0;i<m;i++)
{
while(k>0 && a[k]!=b[i])
k=p[k-1];
if (a[k]==b[i])
k++;
if (k==n) { ap++; v[ap]=i-n+1; }
}
g<<ap<<"\n";
for(i=1;i<=ap;i++)
g<<v[i]<<" ";
return 0;
}