Pagini recente » Cod sursa (job #1243261) | Cod sursa (job #494417) | Cod sursa (job #1816058) | Cod sursa (job #1983558) | Cod sursa (job #1562666)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[2000001];
char B[2000001];
int pi[2000001];
int poz[1001],nrpoz;
int lenA,lenB;
void genPI()
{
int k=0;
pi[0]=0;
for(int i=1;i<=lenA-1;i++)
{
while(k>0 && A[i]!=A[k])
k=pi[k-1];
if(A[k]==A[i])
k++;
pi[i]=k;
}
}
int main()
{
int k;
in>>A>>B;
lenA=strlen(A);
lenB=strlen(B);
genPI();
//for(int i=0;i<=lenA-1;i++) out<<pi[i]<<" ";
k=0;
for(int i=0;i<=lenB-1;i++)
{
while(k>0 && B[i]!=A[k])
k=pi[k-1];
if(A[k]==B[i])
k++;
if(k==lenA)
{
nrpoz++;
if(nrpoz<=1000)
poz[nrpoz]=i-lenA+1;
}
}
out<<nrpoz<<"\n";
if(nrpoz>1000)
nrpoz=1000;
for(int i=1;i<=nrpoz;i++)
out<<poz[i]<<" ";
return 0;
}