CFR 432 D. Prefixes and Suffixes ( Z algorithm )

Problem - 432D - Codeforces

題意：
給一個字串，分別對所有前綴和後綴相等的子字串算出該子字串出現幾次，並按長度由小至大輸出。

資料規模：
1 ≤ |S| ≤ 1e5

解法：
無法 hash，因為這種題目需要利用前綴後綴那種字串本身的特性。所以來用 Z 算法吧！
先知道 Z 算法是什麼：
線性時間內可以預處理出一個字串的每個後綴分別對原字串的最常共同前綴長度。
以這題來說，如果能有這些 Z value，顯然可以常數時間進行後綴和前綴的匹配，又因為知道每個後綴對原字串的 LCP，可以預處理出至少和原字串有某個 LCP 長度的子字串有幾個。
至於 Z Value 的計算方式：
http://codeforces.com/blog/entry/3107

時間 / 空間複雜度：
O( N )

string seq;

void init(){
  cin >> seq;
}

vi Z;

void compute_Z_value( vi &Z, const string &seq ){
  Z = vi( seq.size() );
  Z[ 0 ] = seq.size(); // usually people put 0
  for( int i = 1, L = 0, R = 0; i < seq.size(); ++i ){
    if( R < i ){
      L = R = i;
      while( R < seq.size() and seq[ R - L ] == seq[ R ] ) ++R;
      Z[ i ] = R - L;
      --R;
    } else{
      int k = i - L;
      if( Z[ k ] < R - i + 1 ){
        Z[ i ] = Z[ k ];
      } else{
        L = i;
        while( R < seq.size() and seq[ R - L ] == seq[ R ] ) ++R;
        Z[ i ] = R - L;
        --R;
      }
    }
  }  
}

vp ans;

void preprocess(){
  compute_Z_value( Z, seq );
  vi ss( seq.size() + 1 );
  for( int i = 0; i < Z.size(); ++i ){
    ++ss[ Z[ i ] ];
  }
  for( int i = seq.size() - 1; i >= 0; --i ){
    ss[ i ] += ss[ i + 1 ];
  }
  for( int i = 1; i <= seq.size(); ++i ){
    if( Z[ seq.size() - i ] == i ){
      ans.emplace_back( i, ss[ i ] );
    }
  }
}

void solve(){
  cout << ans.size() << endl;
  for( int i = 0; i < ans.size(); ++i ){
    cout << ans[ i ].first << " " << ans[ i ].second << endl;
  }
}