Cod sursa(job #947161)
#include <vector>
#include <string>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 2000011;
int nfa[NMAX];
vector<int> match;
string pattern, txt;
void buildNFA()
{
int M, i, j;
M = pattern.size();
nfa[0] = nfa[1] = 0;
for(i = 2, j = 0; i <= M; ++i)
{
for(; pattern[i - 1] != pattern[j] && j; j = nfa[j]);
if(pattern[i - 1] == pattern[j]) ++j;
nfa[i] = j;
}
}
void KMP()
{
int N, M, i, j;
N = txt.size();
M = pattern.size();
buildNFA();
match.reserve(N);
pattern.push_back(' ');
for(i = j = 0; i < N; )
{
if(pattern[j] == txt[i])
{
++i, ++j;
if(M == j)
{
match.push_back(i - M);
}
}
else if(j)
j = nfa[j];
else ++i;
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, pattern);
getline(in, txt);
KMP();
out << match.size() << '\n';
copy(match.begin(), match.begin() + min((size_t)1000, match.size()), ostream_iterator<int>(out, " "));
return EXIT_SUCCESS;
}