Pagini recente » Cod sursa (job #1869302) | Cod sursa (job #2531695) | Cod sursa (job #1284228) | Cod sursa (job #2941271) | Cod sursa (job #2716543)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
char a[2000005],b[2000005];
int save[2000005];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n,m,pi[2000002],cnt=0;
in>>(a+1)>>(b+1);
n=strlen(a+1);
m=strlen(b+1);
pi[1]=0;
int lung =0;
for(int i=2;i<=n;i++)
{
while(lung>0 && a[i]!=a[lung+1])
{
lung=pi[lung];
}
if(a[i]==a[lung+1])
{
lung++;
}
pi[i]=lung;
}
lung=0;
for(int i=1;i<=m;i++)
{
while(lung>0 && b[i]!=a[lung+1])
{
lung=pi[lung];
}
if(b[i]==a[lung+1])
{
lung++;
}
if(lung==n)
{
save[cnt++]=i-n;
}
}
out<<cnt<<"\n";
cnt=min(cnt,1000);
for(int i=0;i<cnt;i++)
{
out<<save[i]<<" ";
}
return 0;
}