Pagini recente » Cod sursa (job #386798) | Cod sursa (job #2910074) | Cod sursa (job #2444852) | Cod sursa (job #3247025) | Cod sursa (job #1879620)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>prefix(string pattern)
{
int k = 0;
vector<int>pi(pattern.size(),0);
for (int i = 2; i <= pattern.size(); ++i)
{
while (k > 0 && pattern[k+1] != pattern[i])
k = pi[k];
if (pattern[k+1] == pattern[i])
k++;
pi[i] = k;
}
return pi;
}
vector<int>KMP(string subsir,string sir)
{
int k = 0 , m = subsir.size();
vector<int>answ;
vector<int>pi = prefix(subsir);
for(int i = 1; i <= sir.size(); ++i)
{
while (k > 0 && subsir[k+1] != sir[i])
k = pi[k];
if (subsir[k+1] == sir[i])
k++;
if (k == m - 1)
{
answ.push_back(i-m+1);
k = pi[k];
}
}
return answ;
}
int main()
{
string A,B,S;
getline(fin,S);
B = " ";
B += S;
getline(fin,S);
A = " ";
A += S;
vector<int>answ = KMP(B,A);
int d = answ.size();
int length = min(d,1000);
fout << length << "\n";
for (int i = 0; i < length; ++i)
fout << answ[i] << " ";
return 0;
}