ค้นหาสตริงที่ดีทั้งหมดใน C++

สมมติว่าเรามีสองสตริง s1 และ s2 ขนาดของสตริงเหล่านี้คือ n และเรายังมีสตริงอื่นที่เรียกว่า evil เราต้องหาจำนวนเอ็นดี

สตริงเรียกว่าดีเมื่อขนาดของมันคือ n มันมากกว่าหรือเท่ากับ s1 ตามตัวอักษร มันเล็กกว่าหรือเท่ากับ s2 ตามตัวอักษร และไม่มีความชั่วร้ายเป็นสตริงย่อย คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืนโมดูลคำตอบ 10^9 + 7

ดังนั้น หากอินพุตเป็น n =2, s1 ="bb", s2 ="db", evil ="a" ผลลัพธ์จะเป็น 51 เนื่องจากมีสตริงดี 25 สตริงที่ขึ้นต้นด้วย b "bb", "bc", "bd", ... "bz" จากนั้นมีสตริงที่ดี 25 สตริงที่ขึ้นต้นด้วย "cb", "cc", "cd",..., "cz" และอีกรายการหนึ่ง สตริงที่มี d คือ "db"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=500, M :=50

• กำหนดขนาดอาร์เรย์ dp:(N+1) x (M+1) x 2

• กำหนดขนาดอาร์เรย์ tr:(M+1) x 26

• ม :=1^9 + 7

• กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

• กลับ ((a mod m) + (b mod m)) mod m

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา n, s, e,

• กลับอาร์เรย์ e

• เติม tr และ dp ด้วย 0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ e อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • f :=สตริงย่อยของ e จากดัชนี 0 ถึง i - 1

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <26 อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ns :=f + (j + ASCII ของ 'a')

    • สำหรับการเริ่มต้น k :=i + 1, (ลด k โดย 1) ทำ −

      • ถ้าสตริงย่อยของ ns จากดัชนี (i + 1 - k) ถึงจุดสิ้นสุดเหมือนกับสตริงย่อยของ efrom index 0 ถึง k-1 ของ e ดังนั้น −

        • tr[i, j] :=k

        • ออกจากวง

• m :=ขนาดของ e

• สำหรับการเริ่มต้น i :=0 เมื่อ i <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • dp[i, j, 0] :=0

    • dp[i, j, 1] :=0

• dp[n, 0, 1] :=1

• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ e อัปเดต (เพิ่ม j ขึ้น 1) ทำ -

    • สำหรับการเริ่มต้น k :=0 เมื่อ k <26 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

      • สำหรับ l ในช่วง (0, 1)

        • ถ้า k> s[i] - ASCII ของ 'a' แล้ว −

          • nl :=0

        • มิฉะนั้นเมื่อ k

          • nl :=1

        • มิฉะนั้น

          • nl :=l

        • dp[i, tr[j, k], nl] :=add(dp[i, tr[j, k], nl], dp[i + 1, j, l])

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ e อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ret :=add(ret, dp[0, i, 1])

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• โอเค :=1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ s1 และ ok ไม่ใช่ศูนย์ ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ตกลง:=1 เมื่อ s1[i] เหมือนกับ ASCII ของ 'a'

• ถ้าไม่โอเคก็ไม่ใช่ศูนย์ ดังนั้น −

  • สำหรับการเริ่มต้น i :=ขนาดของ s1 เมื่อ i>=0, อัปเดต (ลด i โดย 1), do−

    • ถ้า s1[i] ไม่เท่ากับ 'a' ดังนั้น −

      • (ลด s1[i] ลง 1)

      • ออกจากวง

    • s1[i] :=ASCII ของ 'z'

• ซ้าย :=(ถ้าตกลงไม่ใช่ศูนย์ แล้ว 0 มิฉะนั้นจะแก้ (n, s1, ชั่วร้าย))

• ขวา :=แก้ (n, s2, ชั่วร้าย)

• กลับ (ขวา - ซ้าย + ม.) mod m

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int N = 500;
const int M = 50;
int dp[N + 1][M + 1][2];
int tr[M + 1][26];
const lli m = 1e9 + 7;
class Solution {
   public:
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   lli solve(int n, string s, string e){
      reverse(e.begin(), e.end());
      memset(tr, 0, sizeof(tr));
      memset(dp, 0, sizeof(dp));
      for (int i = 0; i < e.size(); i++) {
         string f = e.substr(0, i);
         for (int j = 0; j < 26; j++) {
            string ns = f + (char)(j + 'a');
            for (int k = i + 1;; k--) {
               if (ns.substr(i + 1 - k) == e.substr(0, k)) {
                  tr[i][j] = k;
                  break;
               }
            }
         }
      }
      int m = e.size();
      for (int i = 0; i <= n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = dp[i][j][1] = 0;
         }
      }
      dp[n][0][1] = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = 0; j < e.size(); j++) {
            for (int k = 0; k < 26; k++) {
               for (int l : { 0, 1 }) {
                  int nl;
                  if (k > s[i] - 'a') {
                     nl = 0;
                  }
                  else if (k < s[i] - 'a') {
                     nl = 1;
                  }
                  else
                  nl = l;
                  dp[i][tr[j][k]][nl] = add(dp[i][tr[j][k]]
                  [nl], dp[i + 1][j][l]);
               }
            }
         }
      }
      lli ret = 0;
      for (int i = 0; i < e.size(); i++) {
         ret = add(ret, dp[0][i][1]);
      }
      return ret;
   }
   int findGoodStrings(int n, string s1, string s2, string evil) {
      bool ok = 1;
      for (int i = 0; i < s1.size() && ok; i++) {
         ok = s1[i] == 'a';
      }
      if (!ok) {
         for (int i = s1.size() - 1; i >= 0; i--) {
            if (s1[i] != 'a') {
               s1[i]--;
               break;
            }
            s1[i] = 'z';
         }
      }
      int left = ok ? 0 : solve(n, s1, evil);
      int right = solve(n, s2, evil);
      return (right - left + m) % m;
   }
};
main(){
   Solution ob;
   cout << (ob.findGoodStrings(2, "bb", "db", "a"));
}

อินพุต

2, "bb", "db", "a"

ผลลัพธ์

51