Pagini recente » Cod sursa (job #2502534) | Cod sursa (job #1586778) | Cod sursa (job #2398775) | Cod sursa (job #1798127) | Cod sursa (job #2032727)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> ComputeLPS(string P)
{
vector<int> lps(P.size(), 0);
lps[0] = -1;
int k = -1;
for (int i = 1; i < lps.size(); i++)
{
while (k >= 0 && P[k + 1] != P[i])
{
k = lps[k];
}
if (P[k + 1] == P[i])
k++;
lps[i] = k;
}
return lps;
}
vector<int> KMP(string T, string P)
{
vector<int> lps = ComputeLPS(P);
vector<int> occurrences;
int k = -1;
for (int i = 0; i < T.size(); i++)
{
while (k >= 0 && P[k + 1] != T[i])
{
k = lps[k];
}
if (P[k + 1] == T[i])
k++;
if (k == P.size() - 1)
{
occurrences.push_back( i - P.size() + 1);
k = lps[k];
}
}
return occurrences;
}
int main()
{
string A, B;
in >> A >> B;
vector<int> occ = KMP(B, A);
out << occ.size() << endl;
for (int i = 0; i< occ.size() && i < 1000; i++)
{
out << occ[i] << ' ';
}
}