Pagini recente » Cod sursa (job #97834) | Cod sursa (job #2724501) | Cod sursa (job #948585) | Cod sursa (job #687975) | Cod sursa (job #3276008)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,poz[2000200];
char a[2000200],b[2000200];
vector <int> rez;
void prefix()
{
int k=0;
poz[1]=0;
for(int i=2; i<=m; i++)
{
while(k and b[k+1]!=b[i])
k=poz[k];
if(b[k+1]==b[i])
k++;
poz[i]=k;
}
}
int32_t main()
{
f>>b>>a, n=strlen(a), m=strlen(b);
for(int i=n; i>=1; i--)
a[i]=a[i-1]; a[0]=' ';
for(int i=m; i>=1; i--)
b[i]=b[i-1]; b[0]=' ';
prefix();
int j=0;
for(int i=1; i<=n; i++)
{
while(j and b[j+1]!=a[i])
j=poz[j];
if(a[i]==b[j+1])
j++;
if(j==m)
{
rez.push_back(i-j);
if(rez.size()==1000)
break;
}
}
g<<rez.size()<<'\n';
for(auto it:rez)
g<<it<<' ';
return 0;
}