给定字符串A和另一个字符串B。查找任何B的排列是否存在作为A的子字符串。
例如，
如果A =“encyclopedia”
如果B ="dep"，则返回true，因为"ped"是“dep”的排列，并且"ped"是A的子字符串。
My solution->
if length(A)=n and length(B)=m
I did this in 0((n-m+1)*m) by sorting B and then checking A
with window size of m each time.
我需要找到一个更好、更快的解决方案。
基于使用短字符串的窗口大小检查长字符串。由于排列仅改变字符的位置，因此排序后的字符串将始终相同。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main ()
{
string shortone = "abbc";
string longone ="cbabadcbbabbcbabaabccbabc";
int s_length = shortone.length ();
int l_length = longone.length ();
string sub_string;
string unsorted_substring; // only for printing
// sort the short one
sort (shortone.begin (), shortone.end ());
if (l_length > s_length)
{
for (int i = 0; i <= l_length - s_length; i++){
sub_string = "";
//Move the window
sub_string = longone.substr (i, s_length);
unsorted_substring=sub_string;
// sort the substring window
sort (sub_string.begin (), sub_string.end ());
if (shortone == sub_string)
{
cout << "substring is :" << unsorted_substring << '\t' <<
"match found at the position: " << i << endl;
}
}
}
return 0;
}
- 在
- 对于A的每个长度为m的窗口，做同样的操作，但将它们存储在
- j_random_hackerfreqB [i]中累加字符i在字符串B中出现的次数。（例如，在您的示例中，freqB ['d'] == freqB ['e'] == freqB ['p'] == 1，对于所有其他字符i，freqB [i] == 0。）freqA []中，然后检查是否对于每个字符i，freqA[i] == freqB[i]。如果是这样，则表示匹配成功。要从从位置j开始的长度为m的窗口移动到下一个窗口，您需要执行--freqA[A[j]]和++freqA[A[j+m]]。