Pagini recente » Cod sursa (job #367960) | Cod sursa (job #1681627) | Cod sursa (job #1378738) | Cod sursa (job #2408765) | Cod sursa (job #3002289)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5;
string a;
string b;
int p[NMAX];
vector<int>v;
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()
{
int n,m,i,j,kon=0;
fin>>a>>b;
n=a.size();
m=b.size();
kmp(n);
int k=0;
for(j=0;j<m;j++)
{
while(b[j]!=a[k] && k>0)
k=p[k-1];
if(b[j]==a[k])
k++;
if(k==n)
{
kon++;
v.push_back(j-n+1);
}
}
fout<<v.size()<<"\n";
for(auto i:v)
fout<<i<<" ";
return 0;
}