Pagini recente » Cod sursa (job #939004) | Cod sursa (job #1267525) | Cod sursa (job #2655821) | Cod sursa (job #2672711) | Cod sursa (job #2132809)
#include <fstream>
#include <vector>
#include <algorithm>
#include <list>
#include <array>
#include <vector>
#include <string>
using namespace std;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
int * getPrefix(string& P)
{
int m = P.size()-1;
int* pi = new int[m+1]{};
pi[1]=0;
int k = 0;
for(int q = 2 ; q<= m ; q++)
{
while(k>0 && P[k+1]!= P[q])
k = pi[k];
if(P[k+1] == P[q])
k++;
pi[q] = k;
}
return pi;
}
void kmp(string& T, string& P, vector<int>& res)
{
int n = T.size()-1;
int m = P.size()-1;
int* pi = getPrefix(P);
int q = 0;
for(int i = 1 ; i <= n ; i++)
{
while(q>0 && P[q+1] != T[i])
q = pi[q];
if(P[q+1] == T[i])
q++;
if(q == m)
{
res.push_back(i-m);
q = pi[q];
}
}
}
int main()
{
string w,s;
in >> w;
in >> s;
vector<int> P;
w.resize(w.size()+1);
for(int i = w.size()-1; i>=0 ; i--)
w[i+1] = w[i];
s.resize(s.size()+1);
for(int i = s.size()-1; i>=0 ; i--)
s[i+1] = s[i];
if(w.size()<=s.size())
kmp(s,w,P);
out << P.size()<<'\n';
int sz =(P.size()<1000?P.size():1000);
for(int i = 0 ; i< sz ; i++)
out<<P[i]<<" ";
return 0;
}