Pagini recente » Cod sursa (job #1780345) | Cod sursa (job #2410851) | Cod sursa (job #1110055) | Istoria paginii runda/cnrv_4 | Cod sursa (job #2363992)
//Algoritmul KMP
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
#define LMax 2000001
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[LMax],B[LMax];
int v[LMax],sol[LMax];
int minim(int x,int y)
{
if(x<y)
return x;
return y;
}
void citire()
{
f.getline(A,LMax);
f.getline(B,LMax);
f.close();
}
void prefix(int n)
{
v[0]=0;
int i=1,j=0;
while(i<=n)
{
if(A[j]==A[i])
{
v[i]=j+1;
i++; j++;
}
else if(j>0)
j=v[j-1];
else
{
v[i]=0;
i++;
}
}
}
void solutie()
{
int l1,l2,j=0,i=0;
short int contor=0;
l1=strlen(A);
l2=strlen(B);
prefix(l1-1);
while(i<l2)
{
if(B[i]==A[j])
if(j==l1-1)
{
sol[++contor]=i-l1+1;
if(contor==1000)
break;
j=v[j-1];
}
else
{
i++;
j++;
}
else if(j>0)
j=v[j-1];
else
i++;
}
g<<contor<<'\n';
for(short int i=1;i<=minim(contor,1000);i++)
g<<sol[i]<<" ";
g.close();
}
int main()
{
citire();
solutie();
return 0;
}