Pagini recente » Cod sursa (job #2809867) | Cod sursa (job #1556330) | Cod sursa (job #2497166) | Cod sursa (job #1709867) | Cod sursa (job #2896814)
#include <iostream>
#include <fstream>
using namespace std;
#define DIM 2000001
int pi[DIM],n,m,rasp[DIM],r;
string P,T;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calcul_pi_prefix(){
int k=0;
for(int q=2;q<=m;q++){
while(k>0 && P[k+1]!=P[q])
{
k=pi[q];
}
if(P[k+1]==P[q])
{
k++;
}
pi[q]=k;
}
}
void potrivire_KMP(){
calcul_pi_prefix();
int q=0;
for(int i=1;i<=n;i++)
{
while(q>0 && P[q+1]!=T[i]){
q=pi[q];
}
if(P[q+1]==T[i])
{
q++;
}
if(q==m)
{
rasp[r]=i-m;
r++;
q=pi[q];
}
}
}
int main(){
fin>>P>>T;
P.resize(P.length()+1);
T.resize(T.length()+1);
m=P.length()-1;n=T.length()-1;
for(int i=m;i>=1;i--)
{
P[i]=P[i-1];
}
for(int i=n;i>=1;i--)
{
T[i]=T[i-1];
}
potrivire_KMP();
fout<<r<<'\n';
for(int i=0;i<r;i++){
fout<<rasp[i]<<' ';
}
}