Pagini recente » Cod sursa (job #1447192) | Cod sursa (job #1134950) | Cod sursa (job #1458821) | Cod sursa (job #2140152) | Cod sursa (job #2632370)
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
void prefix(char *A, int *pi){
int k = 0;
for(int i = 1; i < strlen(A); i++){
while(k && A[k] != A[i])
k = pi[k];
if(A[k] == A[i]) k++;
pi[i] = k;
}
}
void print(vector<int> ans, FILE *fout){
fprintf(fout, "%ld\n", ans.size());
for(int i = 0; i < ans.size(); i++)
fprintf(fout, "%d ", ans[i]);
}
void solve(char *A, char *B, int *pi, FILE *fout){
int k = 0;
vector<int> ans;
for(int i = 0; i < strlen(B); i++){
while(k > 0 && A[k] != B[i])
k = pi[k];
if(A[k] == B[i])
k++;
if(k == strlen(A)){
ans.push_back(i - strlen(A) + 1);
k = pi[k - 1];
}
}
print(ans, fout);
}
int main(){
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char A[2000000], B[2000000];
int *pi = (int*) calloc(strlen(A), sizeof(int));
fscanf(fin, "%s%s", A, B);
prefix(A, pi);
solve(A, B, pi, fout);
}