Pagini recente » Cod sursa (job #524861) | Cod sursa (job #2480959) | Cod sursa (job #2751084) | Cod sursa (job #835025) | Cod sursa (job #1219837)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char A[2000005],B[2000005];
vector<int> Ans;
int pi[2000005];
void make_prefix(char A[]){
int q = 0, N = strlen(A+1) - 1;
pi[1] = 0;
for(int i = 2; i <= N; i++){
while(q && A[i] != A[q+1])
q = pi[q];
if(A[i] == A[q+1])
q++;
pi[i] = q;
}
}
void match_KMP(char A[],char B[]){
int N = strlen(A+1) - 1;
int M = strlen(B+1) - 1;
int q = 0;
for(int i = 1; i <= M; i++){
while(q && A[q+1] != B[i])
q = pi[q];
if(B[i] == A[q+1])
q++;
if(q == N)
Ans.push_back(i-N);
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A+1,sizeof(A),stdin);
fgets(B+1,sizeof(B),stdin);
make_prefix(A);
match_KMP(A,B);
int Matches = Ans.size();
printf("%d\n",Matches);
if(Matches > 1000) Matches = 1000;
for(int i = 0; i < Matches; i++){
printf("%d ",Ans[i]);
}
}