Pagini recente » Cod sursa (job #3141007) | Cod sursa (job #2718248) | Cod sursa (job #2390220) | Cod sursa (job #1933278) | Cod sursa (job #1911753)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000010
using namespace std;
char A[NMAX],B[NMAX];
int pi[NMAX],pos[2000];
void prefix()
{
int i,k = 0,n = strlen(A);
pi[1] = k;
for(i=2;i<=n;i++)
{
while(k && A[k+1]!=A[i])
k = pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
int main()
{
int i,nrpos=0;
A[0] = B[0] = '0';
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(A+1,NMAX);
f.getline(B+1,NMAX);
int m = strlen(A);
int n = strlen(B);
prefix();
int k = 0;
for(i=1;i<=n;i++)
{
while(k && A[k+1]!=B[i])
k = pi[k];
if(A[k+1] == B[i])
k++;
if(k + 1==m)
{
k = pi[k];
pos[nrpos++] = i - m + 1;
}
}
g<<nrpos<<"\n";
for(i=0;i<nrpos;i++)
g<<pos[i]<<" ";
}