Pagini recente » Cod sursa (job #1834209) | Cod sursa (job #1870471) | Cod sursa (job #417881) | Cod sursa (job #1157650) | Cod sursa (job #2356513)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,i,k,kmp[100010];
vector<int> ans;
string S1,S2;
int main()
{
f>>S1>>S2;
n=S1.size();
for(i=2;i<=n;i++)
{
while((S1[k]!=S1[i-1])&&k)
k=kmp[k];
if(S1[k]==S1[i-1])
k++;
kmp[i]=k;
}
k=0;
n=S2.size();
for(i=1;i<=n;i++)
{
while(S1[k]!=S2[i-1]&&k)
k=kmp[k];
if(S1[k]==S2[i-1])
k++;
if(k==S1.size())
ans.push_back(i);
}
g<<ans.size()<<'\n';
for(i=0;i<1000&&i<ans.size();i++)
g<<ans[i]-S1.size()<<' ';
return 0;
}