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