Pagini recente » Cod sursa (job #1279894) | Cod sursa (job #3254920) | Cod sursa (job #2852783) | Cod sursa (job #1504197) | Cod sursa (job #2056581)
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#define DN 2000010
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
vector<int> v;
int la,lb,pi[DN];
void f()
{
int i,k=0;
pi[0]=pi[1]=0;
for(i=2;i<=la;i++)
{
while(k>0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i]) k++;
pi[i]=k;
}
}
int main()
{
int poz=0,r=0,i;
fin>>a>>b;
la=a.size();
lb=b.size();
a='0'+a;
b='0'+b;
f();
for(i=1;i<=lb;i++)
{
while(poz>0 && a[poz+1]!=b[i]) poz=pi[poz];
if(a[poz+1]==b[i]) poz++;
if(poz==la)
{
r++;
if(r<1000) v.push_back(i-la);
poz=pi[poz];
}
}
fout<<r<<"\n";
if(r>1000) r=1000;
for(i=0;i<r;i++)
fout<<v[i]<<" ";
}