Pagini recente » Cod sursa (job #2494323) | Borderou de evaluare (job #2598823) | Borderou de evaluare (job #2004558) | Cod sursa (job #2372411) | Cod sursa (job #1967863)
#include <bits/stdc++.h>
#define maxN 2000002
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
using namespace std;
int m, n, F[maxN];
char pattern[maxN], text[maxN];
vector <int> sol;
void failure_function(){
F[0] = F[1] = 0; // always true
for(int i = 2; i <= m; i++){
// j is the index of the largest next partial match
// (the largest suffix/prefix) of the string under
// index i - 1
int j = F[i - 1];
for( ; ; ) {
// check to see if the last character of string i -
// - pattern[i - 1] "expands" the current "candidate"
// best partial match - the prefix under index j
if(pattern[j] == pattern[i - 1]) {
F[i] = j + 1; break;
}
// if we cannot "expand" even the empty string
if(j == 0) { F[i] = 0; break; }
// else go to the next best "candidate" partial match
j = F[j];
}
}
}
void KMP(){
// let n be the size of the text, m the
// size of the pattern, and F[] - the
// "failure function"
failure_function();
int i = 0; // the initial state of the automaton is
// the empty string
int j = 0; // the first character of the text
for( ; ; ) {
if(j == n) break; // we reached the end of the text
// if the current character of the text "expands" the
// current match
if(text[j] == pattern[i]) {
i++; // change the state of the automaton
j++; // get the next character from the text
if(i == m) // match found
sol.push_back(j);
}
// if the current state is not zero (we have not
// reached the empty string yet) we try to
// "expand" the next best (largest) match
else if(i > 0) i = F[i];
// if we reached the empty string and failed to
// "expand" even it; we go to the next
// character from the text, the state of the
// automaton remains zero
else j++;
}
}
void write(){
printf("%d\n", (int)sol.size());
for(int i = 0; i < sol.size(); ++ i){
if(i == 1000)
break;
printf("%d ", sol[i] - m);
}
}
int main(){
gets(pattern);
m = strlen(pattern);
gets(text);
n = strlen(text);
KMP();
write();
}