Pagini recente » Cod sursa (job #1490512) | Cod sursa (job #1957208) | Cod sursa (job #2630024) | Cod sursa (job #2157697) | Cod sursa (job #1911776)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000010
using namespace std;
char A[NMAX],B[NMAX];
int pi[NMAX],pos[1010];
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;m--;
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==m)
{
k = pi[m];
nrpos++;
if(nrpos<=1000)
pos[nrpos] = i - m;
}
}
g<<nrpos<<"\n";
for(i=1;i<=nrpos;i++)
g<<pos[i]<<" ";
}