โปรแกรมนับจำนวนลำดับย่อยเฉพาะของสตริงใน C++

สมมติว่าเรามีสตริง s เราต้องหาจำนวนลำดับย่อยเฉพาะที่ไม่ว่างของ s หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขผลลัพธ์ด้วย 10^9 + 7

ดังนั้น หากอินพุตเป็นเหมือน s ="xxy" ผลลัพธ์จะเป็น 5 เนื่องจากมีห้าลำดับย่อย:"x", "xx", "xy", "y" และ "xxy"

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

• ม :=10^9 + 7

• n :=ขนาดของ s

• กำหนดตารางอาร์เรย์ขนาด 26

• res :=0

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

  • c :=s[i − 1] − ASCII ของ 'a'

  • curr :=(res + 1 − table[c] + m) mod m

  • res :=(res + curr) mod m

  • table[c] :=(table[c] + curr) mod m

• ผลตอบแทน

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
   int n = s.size();
   vector<int> table(26);
   long long res = 0;
   for (int i = 1; i <= n; ++i) {
      int c = s[i − 1] − 'a';
      int curr = (res + 1 − table[c] + m) % m;
      res = (res + curr) % m;
      table[c] = (table[c] + curr) % m;
   }
   return res;
}
int main(){
   string s = "xxy";
   cout << solve(s);
}

อินพุต

"xxy"

ผลลัพธ์

5