सी ++ में रैपराउंड स्ट्रिंग में अद्वितीय सबस्ट्रिंग्स

मान लीजिए कि हमारे पास "abcdefghijklmnopqrstuvwxyz" की अनंत रैपराउंड स्ट्रिंग है, तो मान s इस तरह दिखेगा - "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

अब हमारे पास एक और स्ट्रिंग p है। हमारा काम यह पता लगाना है कि s में p के कितने अनूठे गैर-रिक्त सबस्ट्रिंग मौजूद हैं। विशेष रूप से, हमारा इनपुट स्ट्रिंग p है और हमें स्ट्रिंग s में p के विभिन्न गैर-रिक्त सबस्ट्रिंग की संख्या को आउटपुट करने की आवश्यकता है।

इसलिए यदि इनपुट "ज़ैब" की तरह है तो आउटपुट 6 होगा। स्ट्रिंग "ज़ैब" के 6 सबस्ट्रिंग "जेड", "ए", "बी", "ज़ा", "एबी", "ज़ैब" हैं। स्ट्रिंग एस

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

• 26 आकार की एक सरणी dp बनाएँ, x :=0 सेट करें

• I के लिए 0 से p के आकार की सीमा में

  • अगर i> 0 और (p[i] – p[i – 1] 1 है या p[i – 1] – p[i] 25 है), तो x को 1 से बढ़ाएं, अन्यथा x सेट करें:=1

  • dp[p[i] - 'a' का ASCII] :=अधिकतम (x, dp[p[i] - 'a' का ASCII])

• रिट:=0

• I के लिए 0 से 25 की सीमा में

  • रिट:=रिट + डीपी[i]

• वापसी रिट

उदाहरण (C++)

आइए हम इसे बेहतर ढंग से समझने के लिए निम्नलिखित कार्यान्वयन को देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findSubstringInWraproundString(string p) {
      vector <int> dp(26);
      int x = 0;
      for(int i = 0; i < p.size(); i++){
         if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
            x++;
         }
         else x = 1;
            dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
      }
      int ret = 0;
      for(int i = 0; i < 26; i++){
         ret += dp[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findSubstringInWraproundString("zab"));
}

इनपुट

"zab"

आउटपुट

6