Pagini recente » Cod sursa (job #1392795) | Cod sursa (job #1560806) | Cod sursa (job #1385042) | Cod sursa (job #1575188) | Cod sursa (job #2729448)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N=2e6+5,NMAX=1000;
char a[N],b[N];
int pred[N];
int main()
{
f>>(1+a)>>(1+b);
f.close();
int m=strlen(1+a),n=strlen(1+b);
pred[1]=0;
int lung =0;
for(int i=2;i<=m;i++)
{
while(lung>0 && a[i]!=a[lung+1])
{
lung=pred[lung];
}
if(a[i]==a[lung+1])
{
lung++;
}
pred[i]=lung;
}
lung=0;
vector <int> rez;
for(int j=1;j<=n;j++)
{
while(lung > 0 && b[j]!=a[lung+1])
{
lung=pred[lung];
}
if(b[j]==a[lung+1])
{
lung++;
}
if(lung==m)
{
rez.push_back(j-m);
}
}
g<<rez.size()<<"\n";
if (rez.size() > NMAX)
{
rez.erase(rez.begin() + NMAX, rez.end());
}
for(auto i:rez)
{
g<<i<<" ";
}
return 0;
}