Pagini recente » Cod sursa (job #1123954) | Cod sursa (job #546145) | Cod sursa (job #2049288) | Cod sursa (job #160612) | Cod sursa (job #2364185)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <set>
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;
//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);
fout << S.size()<<"\n";
int i = 1;
int M = std::min(S.size(), 1000);
for (auto a : S)
{
if (i > M)
break;
fout << a << " ";
i++;
}
//std::cin.get();
return 0;
}