Pagini recente » Cod sursa (job #1038293) | Cod sursa (job #468883) | antrenamentoji | Cod sursa (job #913110) | Cod sursa (job #2853741)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int N = 4e6;
string a, b, s;
long long a_len, b_len, s_len;
long long kmp[N+5], ans[1005];
long long k, cnt;
int main()
{
fin>>a>>b;
s='$'+a+'$'+b;
a_len=a.size();
b_len=b.size();
s_len=s.size();
if(a_len>b_len)
{
fout<<0;
return 0;
}
for(int i=2; i<s_len; i++)
{
while (k!=0 && s[i]!=s[k+1])
k=kmp[k];
if (s[i]==s[k+1])
k++;
kmp[i]=k;
if(a_len == kmp[i])
{
cnt++;
if(cnt<=1000)
ans[cnt]=i-1-2*a_len;
}
}
fout<<cnt<<'\n';
cnt=min(cnt, 1LL*1000);
for(int i=1; i<=cnt; i++)
fout<<ans[i]<<" ";
return 0;
}