Pagini recente » Cod sursa (job #735558) | Cod sursa (job #236184) | Cod sursa (job #2005164) | Cod sursa (job #1718168) | Cod sursa (job #3300524)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX=2*1e6+5;
int f[NMAX];
string p, t;
void pref(string p, int m)
{
int i, k;
f[0]=-1;
for(i=1; i<=m; i++)
{
k=f[i-1];
while(k>=0 && p[k]!=p[i-1]) k=f[k];
f[i]=k+1;
}
}
void kmp(string t, int n, string p, int m)
{
int cnt=0, i=0, k=0;
vector <int> ans;
while(i<=(n-m+1))
{
if(t[i+k]==p[k]) k++;
else if(k==0) i++;
else
{
i+=k-f[k];
k=f[k];
}
if(k==m)
{
cnt++;
if(cnt<=1000) ans.push_back(i);
}
}
cout<<cnt<<'\n';
for(auto i:ans) cout<<i<<' ';
}
int main()
{
cin>>p;
cin>>t;
pref(p, p.size());
kmp(t, t.size(), p, p.size());
return 0;
}