Pagini recente » Cod sursa (job #2275037) | Cod sursa (job #2228442) | Cod sursa (job #233095) | Cod sursa (job #1120209) | Cod sursa (job #2547699)
#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';
for(int i=0;i<c.size();i++)
out<<c[i]<<" ";
}