Pagini recente » Cod sursa (job #1279540) | Cod sursa (job #293872) | Cod sursa (job #1514555) | Cod sursa (job #2248532) | Cod sursa (job #2242443)
#include <cstring>
#include <cstdio>
#define MIN(A,B) (A <= B ? A : B)
#define NMAX 2000005
using namespace std;
FILE* f = freopen("strmatch.in", "r", stdin);
FILE* g = freopen("strmatch.out", "w", stdout);
int lsp[NMAX], matches[NMAX], app;
char text[NMAX], pattern[NMAX];
void read_data(){
gets(pattern + 1, sizeof(pattern));
gets(text + 1, sizeof(text));
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(){
read_data();
solve_kmp();
printf("%d\n", app);
for(int i =1; i<=MIN(1000, app); i++){
printf("%d ", matches[i]);
}
return 0;
}