Pagini recente » Cod sursa (job #876546) | Cod sursa (job #1249917)
#include <fstream>
#include <cstring>
#define SMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[SMAX], B[SMAX];
int fail[SMAX];
int N,nA,nB, countSol, sol[10000];
void prefix()
{
fail[1]=0;
int nod=0;
int i;
for(i=2;i<=nA;i++)
{
while(nod!=0 && A[i]!=A[nod]+1)
nod=fail[nod];
if(A[i]==A[nod+1])
nod++;
fail[i]=nod;
}
}
int main()
{
f.getline(A+1,SMAX);
f.getline(B+1,SMAX);
nA=strlen(A+1);
nB=strlen(B+1);
prefix();
int i,nod=0;
for(i=1;i<=nB;i++)
{
while(nod!=0 && B[i]!=A[nod+1])
nod=fail[nod];
if(B[i]==A[nod+1])
nod++;
if(nod==nA)
{
if(countSol<1000) sol[++countSol]=i-nA;
nod=fail[nod];
}
}
g<<countSol<<'\n';
for(i=1;i<=countSol;i++) g<<sol[i]<<' ';
}