Pagini recente » Cod sursa (job #2172373) | Cod sursa (job #1216795) | Cod sursa (job #209755) | Cod sursa (job #339691) | Cod sursa (job #3215683)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
#define cin fin
#define cout fout
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5;
string a;
string b;
vector<int>v;
int p[NMAX];
void kmp(int n)
{
int i,k=0;
for(i=1;i<n;i++)
{
while(a[i]!=a[k] && k>0)
k=p[k-1];
if(a[i]==a[k])
k++;
p[i]=k;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,i,j;
cin>>a>>b;
n=a.size();
m=b.size();
kmp(n);
int k=0;
for(i=0;i<m;i++)
{
while(b[i]!=a[k] && k>0)
k=p[k-1];
if(b[i]==a[k])
k++;
if(k==n)
v.push_back(i-n+1);
}
cout<<v.size()<<"\n";
int debuff=0;
for(auto i:v)
{
debuff++;
cout<<i<<" ";
if(debuff==1000)
break;
}
return 0;
}