fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. // Hàm tính toán mảng LPS cho xâu B
  7. vector<int> computeLPSArray(const string& B) {
  8.     int m = B.length();
  9.     vector<int> lps(m);
  10.     int len = 0; // Độ dài của tiền tố dài nhất
  11.     lps[0] = 0; // Giá trị khởi đầu luôn là 0
  12.     int i = 1;
  13.  
  14.     while (i < m) {
  15.         if (B[i] == B[len]) {
  16.             len++;
  17.             lps[i] = len;
  18.             i++;
  19.         } else {
  20.             if (len != 0) {
  21.                 len = lps[len - 1];
  22.             } else {
  23.                 lps[i] = 0;
  24.                 i++;
  25.             }
  26.         }
  27.     }
  28.     return lps;
  29. }
  30.  
  31. // Hàm tìm kiếm KMP
  32. vector<int> KMPSearch(const string& A, const string& B) {
  33.     int n = A.length();
  34.     int m = B.length();
  35.     vector<int> lps = computeLPSArray(B);
  36.     vector<int> positions;
  37.  
  38.     int i = 0, j = 0; // Con trỏ cho A và B
  39.     while (i < n) {
  40.         if (B[j] == A[i]) {
  41.             i++;
  42.             j++;
  43.         }
  44.         if (j == m) {
  45.             // Tìm thấy mẫu tại vị trí i - j
  46.             positions.push_back(i - j + 1); // Chỉ số 1-based
  47.             j = lps[j - 1];
  48.         } else if (i < n && B[j] != A[i]) {
  49.             if (j != 0) {
  50.                 j = lps[j - 1];
  51.             } else {
  52.                 i++;
  53.             }
  54.         }
  55.     }
  56.     return positions;
  57. }
  58.  
  59. int main() {
  60.   ios_base::sync_with_stdio(false);
  61.   cin.tie(nullptr);
  62.   string a;
  63.   string b;
  64.   cin >> a >> b;
  65.   vector<int> positions = KMPSearch(a, b);
  66.   for (int pos : positions) {
  67.     cout << pos << ' ';
  68.   }
  69. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
aaaaa
aa
stdout
copy 
1 2 3 4
https://ideone.com/DMGTk4
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!