Pagini recente » Cod sursa (job #1476748) | Cod sursa (job #2645467) | Cod sursa (job #2914319) | Cod sursa (job #876610) | Cod sursa (job #961393)
Cod sursa(job #961393)
using namespace std;
#include<stdio.h>
#include<cstring>
#include<vector>
#include<fstream>
ifstream eu("strmatch.in");
ofstream tu("strmatch.out");
vector<int>::iterator it;
vector<int>Sol;
char A1[2000005],A2[2000005];
int P[2000005],i,j,q,M,N,k,Solutie;
void construim_prefixul()
{
M=strlen(A1)-1;
P[0]=P[1]=0;
for(i=2;i<=M;i++)
{
while(k&&A1[k+1]!=A1[i])
k=P[k];
if(A1[i]==A1[k+1])
k++;
P[i]=k;
}
}
void KMP()
{
construim_prefixul();
N=strlen(A2)-1;
for(i=1;i<=N;++i)
{
while(q&&A2[i]!=A1[q+1])
q=P[q];
if(A2[i]==A1[q+1])
++q;
if(q==M)
{
q=P[M];
Solutie++;
if(Solutie<=1000)
Sol.push_back(i-M);
}
}
}
int main()
{
A1[0]=' ';
A2[0]=' ';
eu>>A1+1;
eu>>A2+1;
KMP();
tu<<Solutie<<"\n";
for(it=Sol.begin();it!=Sol.end();++it)
tu<<*it<<" ";
return 0;}