मान लीजिए स्ट्रिंग s "abcdefghijklmnopqrstuvwxyz" की अनंत रैपराउंड स्ट्रिंग है, इसलिए s का मान ऐसा दिखेगा: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."।
अब हमारे पास एक और स्ट्रिंग p है। हमारा काम यह पता लगाना है कि p के कितने यूनिक नॉन-एम्प्टी सबस्ट्रिंग्स s में मौजूद हैं। विशेष रूप से, हमारा इनपुट स्ट्रिंग p है और हमें p के विभिन्न नॉन-एम्प्टी सबस्ट्रिंग्स की संख्या आउटपुट करनी है जो स्ट्रिंग s में हैं।
उदाहरण के लिए, अगर इनपुट "zab" है तो आउटपुट 6 होगा। "zab" स्ट्रिंग के 6 सबस्ट्रिंग्स "z", "a", "b", "za", "ab", "zab" स्ट्रिंग s में हैं।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
साइज 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] := max(x, dp[p[i] - 'a' का ASCII])
ret := 0
i को 0 से 25 तक लूप करें:
ret := ret + dp[i]
ret लौटाएं
उदाहरण (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;
}
};
int main(){
Solution ob;
cout << (ob.findSubstringInWraproundString("zab"));
}
इनपुट
"zab"
आउटपुट
6