Pagini recente » Cod sursa (job #2306629) | Cod sursa (job #383866) | Cod sursa (job #1329436) | Cod sursa (job #2754330) | Cod sursa (job #806650)
Cod sursa(job #806650)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi ("strmatch.in");
ofstream fo ("strmatch.out");
const int dim = 40005;
char S[dim];
int P[dim], R[1005], N, len;
void cit ()
{
S[0] = '#';
fi >> S + 1; len = strlen (S);
S[len] = '#';
fi >> S + len + 1;
len--;
}
void kmp ()
{
int k = 0;
P[0] = 0;
for (int i = 2; S[i] != 0; i++)
{
while (k > 0 && S[k + 1] != S[i])
k = P[k];
if (S[k + 1] == S[i])
k++;
P[i] = k;
if (P[i] == len)
{
N++;
if (N <= 1000)
R[++R[0]] = i - len - len - 1;
}
}
}
void afi ()
{
fo << N << '\n';
for (int i = 1; i <= R[0]; i++)
fo << R[i] << ' ';
}
int main ()
{
cit ();
kmp ();
afi ();
return 0;
}