Advertisement
Josif_tepe

Untitled

Dec 24th, 2023
750
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5.  
  6. vector<int> preprocess_lps(string pattern) {
  7.     int j = 0, i = 1;
  8.     vector<int> lps((int) pattern.size(), 0);
  9.     lps[0] = 0;
  10.    
  11.     while(i < (int) pattern.size()) {
  12.         if(pattern[i] == pattern[j]) {
  13.             lps[i] = j + 1;
  14.             j++;
  15.             i++;
  16.         }
  17.         else {
  18.             if(j != 0) {
  19.                 j = lps[j - 1];
  20.             }
  21.             else {
  22.                 lps[i] = 0;
  23.                 i++;
  24.             }
  25.         }
  26.     }
  27.     return lps;
  28. }
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(false);
  32.     string s;
  33.     cin >> s;
  34.     vector<int> lps = preprocess_lps(s);
  35.     int n = (int) s.size();
  36.    
  37.     vector<int> dp(n + 1, 0);
  38.     for(int i = 0; i < n; i++) {
  39.         dp[lps[i]]++;
  40.     }
  41.     for(int i = n - 1; i > 0; i--) {
  42.         dp[lps[i - 1]] += dp[i];
  43.     }
  44.     for(int i = 0; i <= n; i++) {
  45.         dp[i]++;
  46.     }
  47.     for(int i = 0; i < n; i++) {
  48.         cout << lps[i] << " " << dp[lps[i]] << " " << endl;
  49.     }
  50.  
  51.    return 0;
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement