Pagini recente » Cod sursa (job #2297836) | Cod sursa (job #2322930) | Cod sursa (job #625074) | Cod sursa (job #842833) | Cod sursa (job #2174187)
#include <bits/stdc++.h>
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
using namespace std;
const int Nmax = 2e6+3;
int n, m;
char patt[Nmax], txt[Nmax];
int lsp[Nmax];
int nrap;
vector <int> sol;
void Kmp(){
int i = 0, j = 0;
while(i < n){
if(patt[j] == txt[i])
j++, i++;
if(j == m){
++ nrap;
if(sol.size() < 1000)
sol.push_back(i-j);
j = lsp[j-1];
}
else if(i < n && patt[j] != txt[i]){
if(j) j = lsp[j-1];
else ++ i;
}
}
}
void Compute_Lsp(){
lsp[0] = 0;
int i = 1, len = 0;
while(i < m){
if(patt[i] == patt[len]){
len++;
lsp[i++] = len;
}else{
if(len != 0) len = lsp[len-1];
else lsp[i++] = 0;
}
}
}
void Write(){
printf("%d\n", nrap);
for(int i : sol)
printf("%d ", i);
}
int main(){
gets(patt), m = strlen(patt);
gets(txt), n = strlen(txt);
Compute_Lsp();
Kmp();
Write();
return 0;
}