सी ++ में एक स्ट्रिंग के अद्वितीय बाद की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें s के गैर-रिक्त अद्वितीय अनुक्रमों की संख्या ज्ञात करनी है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से संशोधित करें।

इसलिए, यदि इनपुट s ="xxy" जैसा है, तो आउटपुट 5 होगा, क्योंकि इसके बाद के पांच क्रम हैं:"x", "xx", "xy", "y" और "xxy"।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मी :=10^9 + 7

• n :=s का आकार

• आकार 26 की एक सरणी तालिका परिभाषित करें

• रेस :=0

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), do−

  • c :=s[i − 1] - 'a' का ASCII

  • curr :=(res + 1 - टेबल[c] + m) मॉड m

  • res :=(res + 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