Pagini recente » Cod sursa (job #1319341) | Cod sursa (job #1689517) | Cod sursa (job #1067205) | Cod sursa (job #911121) | Cod sursa (job #1969518)
#include <stdio.h>
#include <string.h>
#define MAX_LGH 2000005
FILE* fin;
FILE* fout;
char a[MAX_LGH] = { 0, 0 };
char b[MAX_LGH] = { 0, 0 };
int pi[MAX_LGH] = { 0, 0 };
int n;
int m;
int lengths[MAX_LGH] = { 0 };
int crtLgh = 0;
void LoadFiles()
{
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
}
void Init()
{
LoadFiles();
}
void Read()
{
fscanf(fin, "%s", &a[1]);
fscanf(fin, "%s", &b[1]);
n = strlen(&a[1]);
m = strlen(&b[1]);
}
void Prefix()
{
int k = 0;
pi[1] = 0;
for(int i=2;i<=n;i++)
{
while(k > 0 && a[k+1] != a[i])
{
k = pi[k];
}
if(a[k+1] == a[i])
{
k++;
}
pi[i] = k;
}
}
void KMP()
{
int k = 0;
for(int i=1;i<=m;i++)
{
while(k > 0 && b[i] != a[k+1])
{
k = pi[k];
}
if(b[i] == a[k+1])
{
k++;
}
if(k == n)
{
k = pi[n];
//printf("%d\n", i);
if(crtLgh <= 1000)
{
lengths[crtLgh++] = i - n;
}
}
}
}
void Solve()
{
Prefix();
KMP();
}
void Write()
{
fprintf(fout, "%d\n", crtLgh);
for(int i=0;i<crtLgh;i++)
{
fprintf(fout, "%d ", lengths[i]);
}
}
void CloseFiles()
{
fclose(fin);
fclose(fout);
}
void Terminate()
{
CloseFiles();
}
int main(void)
{
Init();
Read();
Solve();
Write();
Terminate();
return 0;
}