Showing posts with label suffix. Show all posts
Showing posts with label suffix. Show all posts

Saturday, December 26, 2020

POJ.3729 Facer’s string

1.Problem
3729 -- Facer’s string (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3.Source Code

 const int MAXN = 50010;  
 int n, N, M, k, K;  
 int Rank[MAXN * 2];  
 int tmp[MAXN * 2];  
 int sa[MAXN * 2];  
 int lcp[MAXN * 2];  
 int s[MAXN * 2];  
 bool compare_sa(const int& i, const int& j) {  
      if (Rank[i] != Rank[j])return Rank[i] < Rank[j];  
      else {  
           int ri = i + k <= n ? Rank[i + k] : -1;  
           int rj = j + k <= n ? Rank[j + k] : -1;  
           return ri < rj;  
      }  
 }  
 void construct_sa(const int *S, int *sa) {  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp(const int *S, int *sa, int *lcp) {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)Rank[sa[i]] = i;  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)h--;  
           for (; j + h < n&&i + h < n; h++) {  
                if (S[j + h] != S[i + h])break;  
           }  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 long long calc(int K) {  
      int A = 0, B = 0;  
      long long res = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                if (B > 0)res += A;  
                A = 0; B = 0;  
           }  
           if (sa[i + 1] < N)A++;  
           if (sa[i + 1] > N) B++;  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (scanf("%d%d%d\n", &N, &M, &K) != EOF) {  
           for (int i = 0; i < N; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           s[N] = '$';  
           for (int i = N + 1; i < N + M + 1; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           n = N + M + 1;  
           s[n] = 0;  
           construct_sa(s, sa);  
           construct_lcp(s, sa, lcp);  
           printf("%lld\n", calc(K) - calc(K+1));  
      }  
 }  

Friday, December 25, 2020

POJ.3415 Common Substrings

1.Problem
3415 -- Common Substrings (poj.org)

2.Idea
Suffix Array
Monotonic Stack

3.Source

 const int MAX_L = 100000 + 1;  
 const int MAX_N = 2 * MAX_L + 1;  
 std::string S;  
 int n, k;  
 int sa[MAX_N + 1], lcp[MAX_N + 1];   
 int Rank[MAX_N + 1], tmp[MAX_N + 1];  
 bool compare_sa(const int i, const int j)  
 {  
      if (Rank[i] != Rank[j])  
      {  
           return Rank[i] < Rank[j];  
      }  
      return (i + k <= n ? Rank[i + k] : -1) < (j + k <= n ? Rank[j + k] : -1);  
 }  
 void construct_sa()  
 {  
      for (int i = 0; i <= n; i++)  
      {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k <<= 1)  
      {  
           std::sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++)  
           {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++)  
           {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp()  
 {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)  
      {  
           Rank[sa[i]] = i;  
      }  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++)  
      {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)  
           {  
                h--;  
           }  
           for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 int Stack[MAX_N][2];  
 long long contribution, top;  
 using namespace std;  
 long long calc(int K, int l1, bool is_s1)  
 {  
      long long ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                top = contribution = 0;  
           }  
           else {  
                int size = 0;  
                if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1)) {  
                     ++size;  
                     contribution += lcp[i] - K + 1;  
                }  
                while (top > 0 && lcp[i] <= Stack[top - 1][0]) {  
                     --top;  
                     contribution -= Stack[top][1] * (Stack[top][0] - lcp[i]);  
                     size += Stack[top][1];  
                }  
                if (size) {  
                     Stack[top][0] = lcp[i];  
                     Stack[top][1] = size;  
                     ++top;  
                }  
                if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) {  
                     ans += contribution;  
                }  
           }  
      }  
      return ans;  
 }  
 void solve()  
 {  
      int k;  
      while (scanf("%d", &k), k) {  
           string s1, s2;  
           cin >> s1 >> s2;  
           int l1 = s1.length();  
           int l2 = s2.length();  
           S = s1 + "$" + s2;  
           n = l1 + l2 + 1;  
           construct_sa();  
           construct_lcp();  
           printf("%lld\n", calc(k, l1, true) + calc(k, l1, false));  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

Thursday, December 24, 2020

POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 bool compare_sa(int i, int j) {  
      if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];  
      int ri = (i + k <= n) ? Rank[i + k] : -1;  
      int rj = (j + k <= n) ? Rank[j + k] : -1;  
      return ri < rj;  
 }  
 void createSA(const string& s, int* sa) {  
      n = s.size();  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? s[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) Rank[i] = tmp[i];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

Wednesday, December 23, 2020

POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const string& s, int* sa) {  
           n = s.size();  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

Tuesday, December 22, 2020

POJ.3581 Sequence

1.Problem
http://poj.org/problem?id=3581

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }