Pagini recente » Cod sursa (job #2126917) | Cod sursa (job #3217354) | Cod sursa (job #859124) | Cod sursa (job #1413394) | Cod sursa (job #1860783)
#include <fstream>
#include <string.h>
#define nMax 2000001
#define solMax 1001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lenA, lenB, k, nrSol;
int pi[nMax], Sol[solMax];
char A[nMax], B[nMax];
int main()
{
fin>>A+1>>B+1;
lenA=strlen(A+1), lenB=strlen(B+1);
for(int i=2; i<=lenA; i++)
{
while(A[i]!=A[k+1] && k)
k=pi[k];
if(A[i]==A[k+1])
k++;
pi[i]=k;
}
k=0;
for(int i=1; i<=lenB; i++)
{
while(B[i]!=A[k+1] && k)
k=pi[k];
if(B[i]==A[k+1])
k++;
if(k==lenA)
{
nrSol++;
if(nrSol<=1000)
Sol[nrSol]=i-lenA;
k=pi[k];
}
}
fout<<nrSol<<'\n';
for(int i=1; i<=min(1000, nrSol); i++)
fout<<Sol[i]<<" ";
}