Longest Common Prefix
(string/longestcommonprefix.cpp)

• View this file on GitHub
• Last update: 2023-03-20 16:01:48+09:00

できること

• query(a,b) – $S$ の末尾辞の中で $a$ 番目に小さいものと $b$ 番目に小さいもののLCPを求める
• lcp(a,b) – $S[a:|S|]$ と $S[b:|S|]$ のLCPを求める

計算量

構築: $O(|S| \log |S|)$

クエリ: $O(\log |S|)$

注意

• $a \neq b$ を仮定している

Depends on

• Suffix Array (string/suffixarray.cpp)

Verified with

• test lcp (test/aoj/2711.test.cpp)
• test/aoj/3063.test.cpp
• test query (test/aoj/3112.test.cpp)
• test/yosupo/number_of_substrings.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "suffixarray.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE

template<typename Seq = string>
struct LongestCommonPrefix{
  SuffixArray<Seq> sa;

  vector<int> ht;
  vector< vector<int> > dat;
  LongestCommonPrefix(const Seq &s):sa(s){
    int n=s.size();
    vector<int> lcp(n,0);

    int t=0;
    lcp[0]=0;
    for(int i=0;i<n;i++){
      int j=sa[sa.rev[i]-1];
      if(t>0) t--;
      for(;j+t<n and i+t<n;t++){
        if(s[j+t]!=s[i+t]) break;
      }
      lcp[sa.rev[i]-1]=t;
    }

    int h=1;
    while((1<<h)<n) h++;
    dat.assign(h,vector<int>(n));
    ht.assign(n+1,0);
    for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n;j++) dat[0][j]=lcp[j];
    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<n;j++)
        dat[i][j]=min(dat[i-1][j],dat[i-1][min(j+p,n-1)]);
  }

  // a, b are indices for suffix array
  int query(int a,int b){
    assert(a!=b);
    if(a>b) swap(a,b);
    int l=b-a;
    return min(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }

  // a, b are indices for string
  int lcp(int a,int b){
    return query(sa.rev[a],sa.rev[b]);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: string/longestcommonprefix.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page