Pagini recente » Cod sursa (job #2857476) | Cod sursa (job #1339006) | Cod sursa (job #1636219) | Cod sursa (job #2399255) | Cod sursa (job #2716530)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
char a[2000000],b[2000000];
int save[1000000];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n,m,pi[2000000],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";
for(int i=0;i<cnt;i++)
{
out<<save[i]<<" ";
}
return 0;
}