Pagini recente » Cod sursa (job #368604) | Cod sursa (job #160215) | Cod sursa (job #2338437) | Cod sursa (job #972463) | Cod sursa (job #2364190)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <set>
#include <algorithm>
std::set<int> S;
void computePrefix(std::string const&P, std::vector<int>&prefixes)
{
int m = P.length();
//prefixes.resize(m + 1);
prefixes[1] = 0;
int k = 0;
for (int q = 2; q <= m; q++)
{
while (k > 0 && P[k] != P[q - 1])
k = prefixes[k];
if (P[k] == P[q - 1])
k++;
prefixes[q] = k;
}
}
void KMP(std::string const&T, std::string const&P)
{
int n = T.length();
int m = P.length();
std::vector<int> prefixes(2000004);
//prefixes[q] is the length of the longest prefix of P that is a proper suffix of Pq.
computePrefix(P, prefixes);
int q = 0;
//for (auto a : prefixes)
// std::cout << a << " ";
for (int i = 1; i <= n; i++)
{
while (q > 0 && P[q] != T[i - 1])
q = prefixes[q];
if (P[q] == T[i - 1])
q++;
if (q == m)
{
S.insert(i - m);
q = prefixes[q];
}
}
}
int main()
{
std::string a, b;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
fin >> a >> b;
KMP(b, a);
int s = S.size();
fout << s<<"\n";
int i = 1;
int M = std::min(s, 1000);
for (auto a : S)
{
if (i > M)
break;
fout << a << " ";
i++;
}
//std::cin.get();
return 0;
}