Pagini recente » Cod sursa (job #2819348) | Cod sursa (job #2554702) | Cod sursa (job #589821) | Cod sursa (job #1536344) | Cod sursa (job #2547703)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const lim=2000001;
char a[lim],b[lim];
int pi[lim],d[lim];
vector < int> c;
int main()
{
in>>a>>b;
int k=0 , n=strlen(a);
pi[1]=0;
for(int i=2;i<=n;i++)
{
while(k>0 && a[i-1]!=a[k])
k=pi[k-1];
if(a[i-1]==a[k])
k++;
pi[i-1]=k;
}
k=0;
int m=strlen(b);
for(int i=1;i<=m;i++)
{
while(k>0 && b[i-1]!=a[k])
k=d[k-1];
if(b[i-1]==a[k])
k++;
d[i-1]=k;
if(k==n) c.push_back(i-k);
}
out<<c.size()<<'\n';
if(c.size()<=1000) for(int i=0;i<c.size();i++)
out<<c[i]<<" ";
else
for(int i=0;i<=1000;i++)
out<<c[i]<<" ";
}