Pagini recente » Cod sursa (job #1369007) | Cod sursa (job #917345) | Cod sursa (job #2396725) | Cod sursa (job #1837554) | Cod sursa (job #1928934)
#include <fstream>
#include <cstring>
#define LMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int sufpre[LMAX];
char s1[LMAX];
char s2[LMAX];
int lg1;
int lg2;
int sol;
int psol[1005];
void citire();
void KMP();
void afisare();
void sufixe_prefixe();
int main()
{
citire();
KMP();
afisare();
fin.close();
fout.close();
return 0;
}
void citire()
{
fin>>s1;
fin>>s2;
lg1=strlen(s1);
lg2=strlen(s2);
}
void sufixe_prefixe()
{
int i;
int index=0;
for (i=1;i<lg1;)
if (s1[i]==s1[index])
{
sufpre[i]=index+1;
index++;
i++;
}
else
if (sufpre[index]!=0)
index=sufpre[index]-1;
else sufpre[i]=0, i++;
}
void KMP()
{
int i;
int j;
sufixe_prefixe();
for (i=0, j=0; i<lg2; )
if (s1[j]==s2[i])
{
i++;
j++;
if (j==lg1)
{
sol++;
if (sol<=1000)
psol[sol]=i-lg1;
j=sufpre[j-1];
}
}
else if (j!=0)
j=sufpre[j-1];
else {
i++;
}
}
void afisare()
{
int i;
fout<<sol<<'\n';
if (sol>1000)
sol=1000;
for (i=1;i<=sol;i++)
fout<<psol[i]<<' ';
fout<<'\n';
}