Pagini recente » Cod sursa (job #2069530) | Cod sursa (job #672530) | Cod sursa (job #1899695) | Clasament FMI No Stress 5 | Cod sursa (job #1926007)
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000005
using namespace std;
char A[N],B[N];
int lga,lgb,P[N],D[N];
vector <int> Sol;
void Read(){
freopen("strmatch.in","r",stdin);
scanf("%s",A+1);
scanf("%s",B+1);
A[0]=' ';B[0]=' ';
lga=strlen(A)-1;lgb=strlen(B)-1;
}
void Prefix(){
int k=0,i;
for (i=2;i<=lga;++i){
while (k && A[i]!=A[k+1]) k=P[k];
if (A[i]==A[k+1]) k++;
P[i]=k;
}
}
void KMP(){
int k,i;
Prefix();
k=0;
for (i=1;i<=lgb;++i){
while (k && B[i]!=A[k+1]) k=P[k];
if (B[i]==A[k+1]) k++;
if (k==lga) {
k=P[lga];
Sol.push_back(i-lga);
}
}
}
void Write(){
int i;
freopen("strmatch.out","w",stdout);
printf("%d\n",Sol.size());
for (int i=0;i<Sol.size() && i<1000;++i)
printf("%d ",Sol[i]);
}
int main()
{
Read();
KMP();
Write();
return 0;
}