Pagini recente » Cod sursa (job #996729) | Cod sursa (job #1564981) | Cod sursa (job #993750) | Cod sursa (job #3290603) | Cod sursa (job #1206215)
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
int P[DIM], S[1010];
char A[DIM], B[DIM];
int n, m, i, q, k;
int main() {
ifstream fin("kmp.in");
ofstream fout("kmp.out");
fin>>A+1; n = strlen(A+1);
fin>>B+1; m = strlen(B+1);
// preprocesare pentru A: A[i] = lungimea maxima a unui sufix al lui A terminat pepozitia i
// care e in acelasi timp prefix (lungime < i)
q = 0;
P[1] = 0;
for (i=2;i<=n;i++) {
// calcule P[i]
while (A[i] != A[q+1] && q!=0)
q = P[q];
if (A[i] == A[q+1])
++q;
P[i] = q;
}
for (i=1;i<=m;i++) {
while (B[i] != A[q+1] && q!=0)
q = P[q];
if (B[i] == A[q+1])
q++;
if (q == n) {
k++;
if (k<=1000)
S[k] = i-n;
q = P[q];
}
}
fout<<k<<"\n";
if (k > 1000)
k = 1000;
for (i=1;i<=k;i++)
fout<<S[i]<<" ";
return 0;
}