Pagini recente » Cod sursa (job #337503) | Cod sursa (job #1928301) | Cod sursa (job #2788516) | Cod sursa (job #1969797) | Cod sursa (job #1969437)
#include <stdio.h>
#include <string.h>
#define MAX_LGH 2000005
FILE* fin;
FILE* fout;
char a[MAX_LGH] = { 0 };
char b[MAX_LGH] = { 0 };
int pi[MAX_LGH] = { 0 };
int n;
int m;
int lengths[MAX_LGH] = { 0 };
int lghCount = 0;
void LoadFiles()
{
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
}
void Init()
{
LoadFiles();
}
void Read()
{
fscanf(fin, "%s", a);
fscanf(fin, "%s", b);
n = strlen(a);
m = strlen(b);
}
void Prefix()
{
int k = 0;
pi[0] = 0;
for(int i=1;i<n;i++)
{
while(a[i] != a[k] && k != pi[k])
{
k = pi[k];
}
if(a[i] == a[k])
{
k++;
}
pi[i] = k;
}
}
void Find()
{
int k = 0;
for(int i=0;i<m;i++)
{
if(b[i] == a[k])
{
k++;
if(k == n)
{
lengths[lghCount++] = i - n+1;
while(k != pi[k] && b[i] != a[k])
{
k = pi[k];
}
i--;
}
}
else
{
while(k != pi[k] && b[i] != a[k])
{
k = pi[k];
}
if(b[i] == a[k])
{
k++;
if(k == n)
{
lengths[lghCount] = i -n + 1;
while(k != pi[k] && b[i] != a[k])
{
k = pi[k];
}
i--;
}
}
}
}
}
void Solve()
{
Prefix();
Find();
}
void Write()
{
fprintf(fout, "%d\n", lghCount);
for(int i=0;i<lghCount;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;
}