Back
Bai4.cpp
Save
// Bai4.cpp #include <bits/stdc++.h> using namespace std; void z_algo(const char *s, int *z) { int n = strlen(s), l = 0, r = 0; for (int i = 1; i < n; i++) { if (i > r) { l = r = i; while (r < n && s[r - l]== s[r]) r++; z[i] = r - l; r --; } else if (z[i - l] < r - i + 1) z[i] = z[i-l]; else { l = i; while (r < n && s[r - l] == s[r]) r ++; z[i] = r - l; r --; } } } int main() { char t[] = "penny fortune exercise child brick marine month child pour unity deer solid defend child straighten child host"; char p[] = "child"; int n = strlen(t) + strlen(p); char *s = (char*)malloc(n * sizeof(char)); int *z = (int*)calloc(n, sizeof(int)); int i = 0; int j = 0; while (p[i] != '\0') { s[i] = p[i]; i++; } while (t[j] != '\0') { s[i + j] = t[j]; j++; } z_algo(s, z); int count = 0; for (int i = 0; i < strlen(s); i++) { if (z[i] == strlen(p)) count++; } cout << "Tu " << p << " xuat hien " << count << " lan" << endl; return 0; }