Pagini recente » Cod sursa (job #213376) | Cod sursa (job #691579) | Cod sursa (job #1623439) | Cod sursa (job #2061682) | Cod sursa (job #2109412)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define pb push_back
vector<int> prfx(string s)
{
int n=s.size(), k=0, i;
vector<int> v{0};
for(i=1;i<n;i++)
{
while(k>0&&s[k]!=s[i])k=v[k-1];
if(s[k]==s[i])k++;
v.pb(k);
}
return v;
}
vector<int> v;
vector<int> KMP(string s, string sb)
{
int n=sb.size(), m=s.size(), q=-1, i;
vector<int> res;
v=prfx(sb);
for(i=0;i<m;i++)
{
while(q>0&&sb[q+1]!=s[i])
q=v[q];
if(sb[q+1]==s[i])q++;
if(q==n-1)res.pb(i-n+1);
}
return res;
}
string A, B;
vector<int> res;
int main()
{
getline(f, B);
getline(f, A);
res=KMP(A, B);
g<<res.size()<<'\n';
for(auto a:res)g<<a<<' ';
f.close();
g.close();
return 0;
}