Pagini recente » Cod sursa (job #613911) | Cod sursa (job #287302) | Cod sursa (job #1020222) | Cod sursa (job #2698851) | Cod sursa (job #259993)
Cod sursa(job #259993)
#include <fstream>
#define MAX 2000020
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s1[MAX],s2[MAX];
int lg1,lg2,v[MAX];
int nr,rez[1005];
void preg()
{
v[1]=0;
int k=0;
for (int i=2;i<=lg2;i++)
{
while (k && s2[k+1]!=s2[i])
k=v[k];
if (s2[k+1]==s2[i])
k++;
v[i]=k;
}
}
void kmp()
{
int k=0;
for (int i=1;i<=lg1;i++)
{
while (k && s2[k+1]!=s1[i])
k=v[k];
if (s2[k+1]==s1[i])
k++;
if (k==lg2)
{
nr++;
if (nr<=1000)
rez[nr]=i-lg2;
k=v[k];
}
}
}
void afisare()
{
fout<<nr<<"\n";
if (nr>1000)
nr=1000;
for (int i=1;i<=nr;i++)
fout<<rez[i]<<" ";
}
void act(char sir[MAX],int &n)
{
if (sir[strlen(sir)-1]=='\n')
sir[strlen(sir-1)]=0;
n=strlen(sir);
for (int i=n;i>0;i--)
sir[i]=sir[i-1];
sir[0]='\0';
}
void citire()
{
fin.getline(s2,MAX);
fin.getline(s1,MAX);
act(s1,lg1);
act(s2,lg2);
}
int main ()
{
citire();
preg();
kmp();
afisare();
return 0;
}