Pagini recente » Cod sursa (job #1642854) | Cod sursa (job #2362680) | Cod sursa (job #2487837) | Cod sursa (job #1618217) | Cod sursa (job #2482967)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define ceva 2000003
using namespace std;
char a[ceva],b[ceva];
int n,m,pref[ceva],nr;
vector<int>sol;
void citire()
{
a[0]=b[0]='*';
ifstream fin("strmatch.in");
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
}
void prefix()
{
int p=0;
for(int i=2;i<=n;i++)
{
while(p>0&&a[i]!=a[p+1])
p=pref[p];
if(a[i]==a[p+1])
++p;
pref[i]=p;
}
}
void kmp()
{
int nrc=0;
for(int i=1;i<=m;i++)
{
if(b[i]==a[nrc+1])
{
nrc++;
if(nrc==n)
{
nrc=pref[n];
sol.push_back(i-n);
nr++;
}
}
else
{
while(b[i]!=a[nrc+1]&&nrc>0)
nrc=pref[nrc];
if(b[i]==a[nrc+1])
nrc++;
}
}
}
void afisare()
{
ofstream fout("strmatch.out");
fout<<nr<<"\n";
if(nr>1000)
nr=1000;
for(int i=0;i<nr;i++)
fout<<sol[i]<<" ";
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}