Cod sursa(job #936243)
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
const int MAXSIZE = 2000011;
const int MAXMATCHES = 1000;
int errorF[MAXSIZE];
vector<int> match;
string pattern, s;
inline int min(int x, int y) {return x <= y ? x : y;}
void buildErrorF()
{
int M = pattern.size(), i, j;
j = errorF[0] = errorF[1] = 0;
for(i = 2; i <= M; ++i)
{
for(; j && pattern[i - 1] != pattern[j]; j = errorF[j]);
if(pattern[i - 1] == pattern[j]) ++j;
errorF[i] = j;
}
}
void KMP()
{
int N = s.size(), M = pattern.size(), i, j;
buildErrorF();
pattern.push_back(' ');
for(i = j = 0; i < N; )
{
if(pattern[j] == s[i])
{
++i, ++j;
if(M == j)
{
match.push_back(i - M);
}
}
else if(j) j = errorF[j];
else ++i;
}
//pattern.erase(pattern.end() - 1);
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, pattern);
getline(in, s);
KMP();
out << match.size() << '\n';
copy(match.begin(), match.begin() + min(MAXMATCHES, match.size()), ostream_iterator<int>(out, " "));
out << '\n';
}