Pagini recente » Cod sursa (job #219007) | Cod sursa (job #861927) | Cod sursa (job #1675237) | Cod sursa (job #620370) | Cod sursa (job #1754970)
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define DX 2000009
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
vector<int> v;
string x,y,aux;
int pre[DX];
void f();
void solv();
int main()
{
int i,j;
fin>>aux;x=' '+aux;
fin>>aux;y=' '+aux;
f();
solv();
fout<<v.size()<<"\n";
for(i=0;i<min((int)v.size(),1000);i++) fout<<v[i]<<" ";
fout<<"\n";
}
void solv()
{
int i,poz=0;
for(i=1;i<y.size();i++)
{
while(poz && x[poz+1]!=y[i]) poz=pre[poz];
if(x[poz+1]==y[i]) poz++;
//cout<<poz<<" "<<i<<"\n";
if(poz==x.size()-1)
{
v.push_back(i-x.size()+1);
}
}
}
void f()
{
int poz=0,i;
for(i=2;i<x.size();i++)
{
while(poz && x[poz+1]!=x[i]) poz=pre[poz];
if(x[poz+1]==x[i]) poz++;
pre[i]=poz;
}
}