Pagini recente » Cod sursa (job #2000974) | Cod sursa (job #132314) | Cod sursa (job #19856) | Cod sursa (job #753025) | Cod sursa (job #395250)
Cod sursa(job #395250)
#include <fstream>
#include <cstring>
#define NMAX 2000100
using namespace std;
char A[NMAX], B[NMAX];
int N, M, Pi[NMAX], nrPot, Pot[NMAX];
void Citeste(void)
{
ifstream fin("strmatch.in");
int i;
fin.getline(A, NMAX);
fin.getline(B, NMAX);
N = strlen(A);
M = strlen(B);
for (i = N; i ; i--)
A[i] = A[i-1];
A[0] = ' ';
for (i = M; i ; i--)
B[i] = B[i - 1];
B[0] = ' ';
fin.close();
}
void KMP(void)
{
int i, k = 0;
for (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;
}
k = 0;
for (i = 1; i <= M; i++)
{
while ( k > 0 && A[k + 1] != B[i])
k = Pi[k];
if (A[k + 1] == B[i])
k++;
if (k == N)
Pot[++nrPot] = i - N;
}
}
void Afisare(void)
{
ofstream fout("strmatch.out");
int i;
fout <<nrPot <<'\n';
for (i = 1; i <= nrPot; i++)
fout <<Pot[i] <<' ';
fout.close();
}
int main()
{
Citeste();
KMP();
Afisare();
return 0;
}