Pagini recente » Cod sursa (job #2914910) | Cod sursa (job #2758765) | Cod sursa (job #2113143) | Cod sursa (job #2096237) | Cod sursa (job #470276)
Cod sursa(job #470276)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
char a[2000003],p[2000003];
int N,M,pi[2000003],nah;
vector<int> q;
ofstream fout("strmatch.out");
void cit()
{
ifstream fin("strmatch.in");
fin.getline(p,2000003);
fin.getline(a,2000003);
N=strlen(a);
M=strlen(p);
int i;
for(i=N;i>=0;i--) a[i+1]=a[i];
for(i=M;i>=0;i--) p[i+1]=p[i];
fin.close();
}
void calc_pi()
{int i,k;
k=0;
pi[1]=0;
cout<<"\n";
for(i=2;i<=M;++i )
{
while(k>0&&p[k+1]!=p[i])
{
k=pi[k];
}
if(p[k+1]==p[i])
k++;
pi[i]=k;
}
}
void kmp()
{int nah=0;
int i,k=0;
calc_pi();
cout<<"\n";
for(i=1;i<=N;++i)
{
while(k>0 && p[k+1]!=a[i])
{
k=pi[k];
}
if(p[k+1]==a[i])
k++;
if(k==M)
{ nah++;
q.push_back(i-M);
k=pi[k];
}
}
fout<<nah<<"\n";
if(nah)
{
for(i=0;i<=nah-1&&i<=999;i++)
fout<<q[i]<<" ";
}
fout<<"\n";
}
int main()
{
cit();
kmp();
fout.close();
return 0;
}