Pagini recente » Cod sursa (job #2751957) | Cod sursa (job #2610230) | Cod sursa (job #2063018) | Cod sursa (job #1658569) | Cod sursa (job #1552542)
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,k,phi[2000010],n,m,v[2000010],nr;
char a[2000010],b[2000010];
void phi1()
{
int i,k;
phi[1]=0;
for (i=2; i<=n; i++)
{
k=phi[i-1];
while (a[i]!=a[k+1] && k>0)
k=phi[k];
if (a[i]==a[k+1]) phi[i]=k+1;
else phi[i]=0;
}
}
int main()
{
f.getline(a,2000100);
f.getline(b,2000100);
for (i=strlen(a); i>0; i--)
a[i]=a[i-1];
for (i=strlen(b); i>0; i--)
b[i]=b[i-1];
n=strlen(a)-1;
m=strlen(b)-1;
a[n+1]=' ';
a[0]=NULL;
b[0]=NULL;
phi1();
for (i=1; i<=m; i++)
{
k=v[i-1];
while (k>0 && b[i]!=a[k+1])
k=phi[k];
if (b[i]==a[k+1])
v[i]=k+1;
else v[i]=0;
}
for (i=1; i<=m; i++)
if (v[i]==n) nr++;
g<<nr<<'\n';
if (nr>1000)
nr=1000;
i=1;
while (nr>0 && i<=m)
{
if (v[i]==n) g<<i-n<<' ',nr--;
i++;
}
f.close();
g.close();
}