Pagini recente » Cod sursa (job #387642) | Cod sursa (job #1898823) | Cod sursa (job #1634794) | Cod sursa (job #2254462) | Cod sursa (job #2356562)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,l,r,zalg[4000010];
vector<int> ans;
string S1,S2;
int main()
{
f>>S1>>S2;n=S1.size();
S1+='$';S1+=S2;l=r=1;m=S1.size();
for(i=2;i<=m;i++)
if(r<i)
{
r=i;
while(S1[r-1]==S1[r-i]&&r<m)
r++;
r--;l=i;
zalg[i]=r-i+1;
}
else
{
zalg[i]=min(zalg[i-l+1],r-i+1);
if(zalg[i]==r-i+1)
{
while(S1[r]==S1[r-i+1]&&r<m)
r++;
zalg[i]=r-i+1;
l=i;
}
}
// cout<<S1<<'\n';
// for(i=1;i<=m;i++)
// cout<<zalg[i]<<' ';
for(i=1;i<=m;i++)
if(zalg[i]==n)
ans.push_back(i-n-2);
g<<ans.size()<<'\n';
for(i=0;i<ans.size()&&i<1000;i++)
g<<ans[i]<<' ';
return 0;
}