Pagini recente » Cod sursa (job #472170) | Cod sursa (job #708166) | Cod sursa (job #2894596) | Cod sursa (job #2765357) | Cod sursa (job #2834494)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
vector <int> rez;
int l[2000005], n, m;
void kmp_preg()
{
int i=1, j=1;
while(i<n)
{
int k=l[i];
while(k>0 && s1[k+1]!=s1[i+1])
k=l[k];
if(s1[i+1]==s1[k+1]) k++;
l[i+1]=k;
i++;
}
}
void KMP()
{
int i=0, k=0;
while(i<m)
{
while(k>0 && s1[k+1]!=s2[i+1])
k=l[k];
if(s1[k+1]==s2[i+1]) k++;
if(k==n)
{
rez.push_back(i-k+1);
k=l[k];
}
i++;
}
}
int main()
{
fin >> s1 >> s2;
n=s1.length();
m=s2.length();
n=min(n, 1000);
m=min(m, 1000);
s1=' '+s1;
s2=' '+s2;
kmp_preg();
//fout << s1 << "\n" << s2;
KMP();
fout << rez.size() << "\n";
for(int i=0; i<rez.size(); i++) fout << rez[i] << " ";
// for(int i=1; i<=n; i++) fout << l[i] << " ";
return 0;
}