Pagini recente » Cod sursa (job #1246658) | Cod sursa (job #1562370) | Cod sursa (job #491931) | Cod sursa (job #2742004) | Cod sursa (job #2989117)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX=2000009;
char stra[NMAX],strb[NMAX];
int aparitii[1005],prefix[NMAX];
void build_prefix(int n)
{
prefix[1]=0;
int len=0;
for(int i=2; i<=n; i++)
{
while(len>0 && stra[i]!=stra[len+1])
len=prefix[len];
if(stra[i]==stra[len+1])
len++;
prefix[i]=len;
}
}
void KMP(int a, int b)
{
int len=0;
int k=0;
for(int i=1; i<=b; i++)
{
while(len>0 &&stra[len+1]!=strb[i])
len=prefix[len];
if(stra[len+1]==strb[i])
len++;
if(len==a)
{
k++;
if(k<=1000)
aparitii[k]=i-a;
len=prefix[len];
}
}
out<<k<<'\n';
for(int i=1; i<=min(1000,k); i++)
{
out<<aparitii[i]<<" ";
}
}
int main()
{
in.getline(stra,NMAX);
in.getline(strb,NMAX);
int lenghta=strlen(stra);
int lenghtb=strlen(strb);
for(int i=lenghtb; i>=1; i--)
strb[i]=strb[i-1];
for(int i=lenghta; i>=1; i--)
stra[i]=stra[i-1];
build_prefix(lenghta);
KMP(lenghta,lenghtb);
return 0;
}