Pagini recente » Cod sursa (job #2297439) | Cod sursa (job #464919) | Cod sursa (job #2362896) | Cod sursa (job #130374) | Cod sursa (job #2242449)
#include <cstring>
#include <cstdio>
#define MIN(A,B) (A <= B ? A : B)
#define NMAX 2000005
using namespace std;
int lsp[NMAX], matches[NMAX], app;
char text[NMAX], pattern[NMAX];
void read_data(){
FILE* f = freopen("strmatch.in", "r", stdin);
gets(pattern + 1);
gets(text + 1);
text[0] = '&';
pattern[0] = '&';
}
void build_lsp(){
int k = 0;
lsp[1] = 0;
int m = strlen(pattern) - 1;
for(int i = 2; i<= m; i++){
while(k > 0 && pattern[i] != pattern[k + 1]){
k = pattern[k];
}
if(pattern[k + 1] == pattern[i]){
k ++;
}
lsp[i] = k;
}
}
void solve_kmp(){
build_lsp();
int n = strlen(text) - 1;
int m = strlen(pattern) - 1;
int q = 0;
for(int i = 1; i<=n; i++){
while(q != 0 && pattern[q + 1] != text[i]){
q = lsp[q];
}
if(pattern[q + 1] == text[i]){
q ++;
}
if(q == m){
app ++;
if(app <= 1000){
matches[app] = i - m;
}
q = lsp[q];
}
}
}
int main(){
FILE* g = freopen("strmatch.out", "w", stdout);
read_data();
solve_kmp();
printf("%d\n", app);
for(int i =1; i<=MIN(1000, app); i++){
printf("%d ", matches[i]);
}
return 0;
}