Pagini recente » Cod sursa (job #1685409) | Cod sursa (job #2811032) | Cod sursa (job #124317) | Cod sursa (job #1402471) | Cod sursa (job #1830848)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char a[100],b[100];
int s[100];
void Citire ()
{
ifstream f ("strmatch.in");
f>>a;
f>>b;
}
void Prefix_Sufix ()
{
int i=1,j=0;
while (i<strlen(a))
{
if (a[j]==a[i])
{
s[i]=j+1;
j++;
}
else
{
while (j!=0)
{
j=s[j-1];
goto nextI;
}
}
i++;
nextI:
;
}
}
void KMP ()
{
ofstream g("strmatch.out");
int i=0,j=0,nra=0,p[100],k=0;
while (i<strlen(b))
{
if (b[i]==a[j])
{
i++;
j++;
if (j==strlen(a))
{
nra++;
p[k++]=i-strlen(a);
}
}
else
{
if (j!=0)
j=s[j-1];
if (b[i]==a[j])
{
i++;
j++;
if (j==strlen(a))
{
nra++;
p[k++]=1;
}
}
else
i++;
}
}
g<<nra<<endl;
for (int i=0;i<k;i++)
g<<p[i]<<" ";
}
int main()
{
Citire ();
Prefix_Sufix();
KMP ();
return 0;
}