Pagini recente » Cod sursa (job #1698710) | Cod sursa (job #255033) | Profil banutraul123 | Cod sursa (job #2402352) | Cod sursa (job #2632502)
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int pi[2000001];
void prefix(char *A, int *pi){
int k = 0;
for(int i = 2; i <= strlen(A); i++){
while(k && A[k + 1] != A[i])
k = pi[k];
if(A[k + 1] == 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 < 1000; i++)
fprintf(fout, "%d ", ans[i]);
}
void solve(char *A, char *B, int *pi, FILE *fout){
int k = 0, size = strlen(B);
vector<int> ans;
for(int i = 0; i < size; i++){
while(k > 0 && A[k + 1] != B[i])
k = pi[k];
if(A[k + 1] == B[i])
k++;
if(k == strlen(A) - 1){
ans.push_back(i - strlen(A) + 2);
k = pi[k];
}
}
print(ans, fout);
}
int main(){
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char A[2000001], B[2000001];
fscanf(fin, "%s%s", A, B);
for(int i = strlen(A); i > 0; i--)
A[i] = A[i - 1];
prefix(A, pi);
solve(A, B, pi, fout);
fclose(fin);
fclose(fout);
}