Pagini recente » Cod sursa (job #1260017) | Cod sursa (job #544464) | Cod sursa (job #365930) | Cod sursa (job #1121427) | Cod sursa (job #1191049)
#include <array>
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 2000011;
const int MAXMATCHES = 1000;
size_t size;
vector<int> match;
array<int, NMAX> f;
void errorFunction(string p)
{
f[0] = f[1] = 0;
for(decltype(p.size()) i = 2; i <= p.size(); ++i)
{
int j;
for(j = f[i - 1]; j && p[j] != p[i - 1]; j = f[j]);
if(p[j] == p[i - 1]) ++j;
f[i] = j;
}
}
void KMP(string p, string s)
{
int N, M, i, j;
N = s.size();
M = p.size();
errorFunction(p);
p.push_back(' ');
s.push_back(' ');
for(i = j = 0; i < N; )
{
if(s[i] == p[j])
{
++i, ++j;
if(M == j)
{
++size;
if(size < MAXMATCHES) match.push_back(i - M);
}
}
else if(j) j = f[j];
else ++i;
}
}
int main()
{
string p, s;
ifstream in{"strmatch.in"};
ofstream out{"strmatch.out"};
getline(in, p);
getline(in, s);
KMP(p, s);
out << size << '\n';
copy(match.begin(), match.end(), ostream_iterator<int>{out, " "});
out << '\n';
return EXIT_SUCCESS;
}