Pagini recente » Cod sursa (job #719698) | Cod sursa (job #3284051) | Cod sursa (job #2076709) | Cod sursa (job #596005) | Cod sursa (job #1331180)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int pi[2000005],pos[1024];
int A,B;
void prefix()
{
int i,q=0;
for(i=2;i<=A;i++)
{
while(q&&a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
q++;
pi[i]=q;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,q=0,n=0;
f.getline(a+1,2000000,'\n');
f.getline(b+1,2000000,'\n');
A=strlen(a+1);
B=strlen(b+1);
prefix();
for (i = 1; i <= B; i++)
{
while (q && a[q+1] != b[i])
q = pi[q];
if (a[q+1] == b[i])
q++;
if (q == A)
{
q = pi[A];
n++;
if (n <= 1000)
pos[n] = i-A;
}
}
g<<q<<endl;
for(i=1;i<=q&&i<=1000;i++)
g<<pos[i]<<" ";
}