Pagini recente » Cod sursa (job #1762113) | Cod sursa (job #417885) | Cod sursa (job #270194) | Cod sursa (job #49859) | Cod sursa (job #1469407)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "strmatch.in";
const char oname[] = "strmatch.out";
int N;
int poz[1005];
ofstream out(oname);
string P, T;
vector<int> getPrefixFunction(const string P)
{
int m = P.length();
vector<int> pr;
pr.push_back(-1);
int k = -1;
for(int q = 1; q < m; q++)
{
while(k >= 0 && P[k+1] != P[q])
k = pr[k];
if(P[k+1] == P[q])
k++;
pr.push_back(k);
}
return pr;
}
void KMP_Matcher(const string T, const string P)
{
int m = P.length();
int t = T.length();
vector<int> pr = getPrefixFunction(P);
int q = -1;
for(int i = 0; i < t; i++)
{
while(q > -1 && P[q+1] != T[i]) q = pr[q];
if(P[q+1] == T[i]) q++;
if(q == m-1)
{
if(N<1000)
poz[N] = i - m +1;
N++;
q = pr[q];
}
}
out << N << '\n';
for(int i = 0; i < N && i < 1000; i++)
out << poz[i] << ' ';
}
int main()
{
ifstream in(iname);
in >> P >> T;
KMP_Matcher(T,P);
return 0;
}