Pagini recente » Cod sursa (job #2937928) | Cod sursa (job #313892) | Cod sursa (job #3234087) | Cod sursa (job #1503762) | Cod sursa (job #906983)
Cod sursa(job #906983)
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;
#define Nmax 2000007
char A[Nmax], B[Nmax];
int n, m, sol, nrsol;
int pi[Nmax];
list <int> poz;
void read(){
A[0] = ' ';
B[0] = ' ';
fgets(A+1, Nmax, stdin);
fgets(B+1, Nmax, stdin);
n = strlen(A);
m = strlen(B);
--n, --m;
fclose(stdin);
}
void kmp(){
int i, k;
pi[0] = 0;
k = 0;
for(i = 2; i < n; ++i){
while(k > 0 && A[k+1] != A[i])
k = pi[k];
if(A[k+1] == A[i]) ++k;
pi[i] = k;
}
k = 0;
for(i = 1; i < m; ++i){
while(k > 0 && A[k+1] != B[i])
k = pi[k];
if(A[k+1] == B[i]) ++k;
if(k == n - 1){
++sol;
if(nrsol < 1000){
poz.push_back(i - n + 1);
++nrsol;
}
}
}
printf("%i\n", sol);
list <int>::iterator it, last;
it = poz.begin();
last = poz.end();
for(; it != last; ++it)
printf("%i ", *it);
printf("\n");
fclose(stdout);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
kmp();
return 0;
}