Pagini recente » Cod sursa (job #1083128) | Cod sursa (job #626621) | Cod sursa (job #2141264) | Cod sursa (job #1263809) | Cod sursa (job #1225846)
#include <fstream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define MX 2000010
char a[MX],b[MX];
int pi[MX], k, i, n,m, ns, sol[1024] ;
int main()
{
freopen("strmatch.in", "r", stdin);
ofstream f2("strmatch.out");
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
n=strlen(a)-1;
m=strlen(b)-1;
for (i=n; i>0; i--)
a[i]=a[i-1];
for (i=m; i>0; i--)
b[i]=b[i-1];
k=0;
pi[1]=0;
for (i=2; i<=n; i++ )
{ while (k>0 && a[k+1]!=a[i] )
k=pi[k];
if (a[k+1]==a[i] )
k++;
pi[i]=k; }
k=0;
for (i=1; i<=m && ns<=1000; i++)
{ while (k>0 && a[k+1]!=b[i] )
k=pi[k];
if (a[k+1]==b[i] )
k++;
if (k==n)
sol[++ns]=i-n;
}
f2<<ns<<"\n";
for (i=1; i<=ns; i++)
f2<<sol[i]<<" ";
f2.close();
return 0;
}