C++での最長の重複部分文字列

文字列Sがあると仮定し、2回以上発生する重複した連続するすべてのサブ文字列を検討します。 （オカレンスが重複する場合があります。）、可能な限り長い長さの重複したサブストリングを見つける必要があります。そのような部分文字列がない場合は、空白の文字列を返します。答えは非常に大きい可能性があるため、mod 10 ^ 9+7で返します。

したがって、入力が「ababbaba」のような場合、出力は「bab」になります

これを解決するには、次の手順に従います-

• m：=1e9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数sub（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）-（b mod m）+ m）mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• アレイパワーを定義する

• 関数ok（）を定義します。これにはx、s、

  が必要です。

• xが0と同じ場合、-

  • 空の文字列を返す

• ハッシュと呼ばれる1つのマップを定義する

• 現在：=0

• 初期化i：=0の場合、i

  • current：=add（mul（current、26）、s [i]-'a'）

• hash [current]：=配列を定義する（1、0）

• n：=sのサイズ

• 初期化i：=xの場合、i

  • current：=sub（current、mul（power [x --1]、s [i --x]-'a'））

  • current：=add（mul（current、26）、s [i]-'a'）

  • countがハッシュのメンバーである場合、-

    • hash [current] −

      のすべて

      • それからx-1までのsの部分文字列がi-x+1からx-1までのsの部分文字列と同じである場合、-

        • sの部分文字列をx-1に返します

  • それ以外の場合

    • hash [current]

      の最後にi--x+1を挿入します

• 空の文字列を返す

• メインの方法から、次のようにします-

• ret：=空の文字列

• n：=Sのサイズ

• power：=サイズnの配列を定義し、これを1で埋めます

• 初期化i：=1の場合、i

  • power [i]：=mul（power [i-1]、26）

• 低：=0、高：=n-1

• 低い<=高い間、実行-

  • 中：=低+（高-低）/ 2

  • temp：=ok（mid、S）

  • tempのサイズが0と同じ場合、-

    • 高：=中-1

  • それ以外の場合

    • tempのサイズ>retのサイズの場合、-

      • ret：=temp

    • 低：=中+ 1

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int m = 1e9 + 7;
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int sub(lli a, lli b){
      return ((a % m) - (b % m) + m) % m;
   }
   int mul(lli a, lli b){
      return ((a % m) * (b % m)) % m;
   }
   vector<int> power;
   string ok(int x, string s){
      if (x == 0)
      return "";
      unordered_map<int, vector<int> > hash;
      lli current = 0;
      for (int i = 0; i < x; i++) {
         current = add(mul(current, 26), s[i] - 'a');
      }
      hash[current] = vector<int>(1, 0);
      int n = s.size();
      for (int i = x; i < n; i++) {
         current = sub(current, mul(power[x - 1], s[i - x] -
         'a'));
         current = add(mul(current, 26), s[i] - 'a');
         if (hash.count(current)) {
            for (auto& it : hash[current]) {
               if (s.substr(it, x) == s.substr(i - x + 1, x)) {
                  return s.substr(it, x);
               }
            }
         } else {
            hash[current].push_back(i - x + 1);
         }
      }
      return "";
   }
   string longestDupSubstring(string S){
      string ret = "";
      int n = S.size();
      power = vector<int>(n, 1);
      for (int i = 1; i < n; i++) {
         power[i] = mul(power[i - 1], 26);
      }
      int low = 0;
      int high = n - 1;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         string temp = ok(mid, S);
         if (temp.size() == 0) {
            high = mid - 1;
         } else {
            if (temp.size() > ret.size())
            ret = temp;
            low = mid + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestDupSubstring("ababbaba"));
}

入力

"ababbaba"

出力

bab