Pagini recente » Cod sursa (job #844193) | Cod sursa (job #269277) | Cod sursa (job #2551742) | Cod sursa (job #2934785) | Cod sursa (job #2140834)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[Nmax],b[Nmax];
int pre[Nmax];
int n,m;
vector<int>sir;
void citire()
{
fin>>(a+1) >> (b+1);
n=strlen(a+1);
m=strlen(b+1);
}
void prefix()
{
int k=0;
for(int i=2;i<=n;++i)
{
while(k>0 && a[k+1]!=a[i])
k=pre[k];
if(a[k+1]==a[i])++k;
pre[i]=k;
}
}
void potrivire()
{
int k=0;
for(int i=1;i<=m;++i)
{
while(k>0 && a[k+1]!=b[i])
k=pre[k];
if(a[k+1]==b[i])
++k;
if(k==n)
sir.push_back(i-n);
}
}
int main()
{
citire();
prefix();
potrivire();
fout<<sir.size()<<"\n";
for(int i=0;i<min(1000,int(sir.size()));++i)
fout<<sir[i]<<" ";
return 0;
}