Pagini recente » Cod sursa (job #1766210) | Cod sursa (job #4424) | Cod sursa (job #531328) | Cod sursa (job #1739153) | Cod sursa (job #3292855)
#include <bits/stdc++.h>
using namespace std;
int kmp[4000005];
string a,b, s="#";
vector<int>sol;
void KMP()
{
for(int i=2; i<s.size(); i++)
{
int k=kmp[i-1];
while(k!=0 && s[k+1]!=s[i])
k=kmp[k];
if(s[k+1]==s[i])
kmp[i]=k+1;
if(kmp[i]==a.size())
sol.push_back(i-2*a.size()-1);
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>a>>b;
s+=a+'#'+b;
KMP();
cout<<sol.size()<<'\n';
for(int i=0; i<min(1000, (int)sol.size()); i++)
cout<<sol[i]<<" ";
return 0;
}