Pagini recente » Cod sursa (job #485237) | Cod sursa (job #1326811) | Cod sursa (job #482454) | Cod sursa (job #655292) | Cod sursa (job #2346908)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream x("strmatch.in");
ofstream y("strmatch.out");
int i,j,k,pi[2000005],v1,v2,nr,poz[1002];
char s1[2000005],s2[2000005];
void kmp()
{
int i=2;
int k=0;
for(i=2;i<=v1;i++)
{
while(k && s1[k+1]!=s1[i])
k=pi[k];
if(s1[k+1]==s1[i])
k++;
pi[i]=k;
}
}
void kmp1 (int &nr)
{
int i=1;
int k=0;
for(i=1;i<=v2;i++)
{
while(k && s1[k+1]!=s2[i])
k=pi[k];
if(s1[k+1]==s2[i])
k++;
if(k==v1)
{
nr++;
if(nr<=1000)
{
poz[nr]=i-k;
}
}
}
}
int main()
{
x>>s1+1;
v1=strlen(s1+1);
x>>s2+1;
v2=strlen(s2+1);
kmp();
kmp1(nr);
y<<nr<<'\n';
for(i=1;i<=nr;i++)
{
y<<poz[i]<<" ";
}
x.close();
y.close();
return 0;
}