Pagini recente » Cod sursa (job #2490438) | Cod sursa (job #1996455) | Cod sursa (job #1186222) | Cod sursa (job #2839385) | Cod sursa (job #1562633)
#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=1;i<=lenB-1;i++)
{
while(k>0 && B[i]!=A[k])
k=pi[k-1];
if(A[k]==B[i])
k++;
if(k==lenA)
{
if(nrpoz+1<=1000)
{
nrpoz++;
poz[nrpoz]=i-lenA+1;
}
}
}
out<<nrpoz<<"\n";
for(int i=1;i<=nrpoz;i++)
out<<poz[i]<<" ";
return 0;
}