string - 查找包含另一个字符串的某些变位词作为子序列的字符串的子字符串数

Question

我们必须找到一个字符串的子字符串的数量，这些子字符串包含另一个字符串的一些变位词作为子序列。

仅当开始或结束位置不同时才认为子串不同。

String="aba"
anotherString="a"

Occurence of "a" in "aba" is as follows :

a     at index 0..0
ab    at index 0..1
aba   at index 0..2
ba    at index 1..2
a     at index 2..2

i.e total of 5 times...so o/p=5
(the start and end points here, are inclusive)

我认为这道题是“字符串中某个子序列的出现次数”和“在包含另一个字符串的所有字符的字符串中找到最小窗口”的应用之一。

但即使在对组合代码进行多次更改后，我也无法提出解决方案。 粘贴我的代码是没有用的，因为我知道我哪里错了。我想知道的是我们如何在没有暴力解决方案的情况下有效地解决这个问题。

代码:

public static void findLengthAndSequence(String str1,String str2){

    int begin=0,biginWith=0,endWith=0,count=0,minLen=Integer.MAX_VALUE,len=0;
    int l=0;

    int [] hasFound=new int[256];
    int [] toFound=new int[256];

    for(int i=0;i<str2.length();++i){           
        toFound[(int)str2.charAt(i)]++;
    }

    for(int end=0;end<str1.length();++end){
        if(toFound[(int)str1.charAt(end)]==0)
            continue;
        hasFound[(int)str1.charAt(end)]++;
        if(hasFound[(int)str1.charAt(end)]<=toFound[(int)str1.charAt(end)]){
            count++;
        }

        if(count==str2.length()){
            l++;        //add this to find number of such anagram in string
            System.out.println("l= "+l+" "+begin+" "+end); 
            while(toFound[(int)str1.charAt(begin)]==0 || hasFound[(int)str1.charAt(begin)]>toFound[(int)str1.charAt(begin)]  )
            {
                if(hasFound[(int)str1.charAt(begin)]>toFound[(int)str1.charAt(begin)]){
                    hasFound[(int)str1.charAt(begin)]-=1;                       
                }
                begin++;
            }//while
        len=end-begin+1;
        if(minLen>len){
            minLen=len;
            endWith=end;
            biginWith=begin;
        }
    }//if   
    }//end

    for(int i=biginWith;i<=endWith;++i){
        System.out.print(""+str1.charAt(i));
    }
}

此代码为上述问题提供输出 =3。 我知道，一旦我到达第一个字符串的末尾，遍历剩余的子字符串后，我就无法检查其中的每个子字符串。

e.g in "aba" my code checks for a,ab,aba.but once I reach the end it will not check   
ba,a .since we need to count this also as they are having different index values.

除了指数时间复杂度的蛮力之外，还有什么方法可以检查每个可能的子字符串..

Answer 1

这是一个简单的解决方案 O(n + m)时间复杂度(我假设字母表的大小是一个常数(其中 n 是第一个字符串的长度(我们要在其中计算子字符串的字符串)，m 是第二个字符串的长度(字谜字符串))。我将调用包含第二个字符串“good”的字谜的子字符串。

1. 让我们定义count(x, y)作为 y 的出现次数字符串中的字符 x .然后是任意字符串 s包含字符串的变位词 t作为子序列当且仅当count(s, c) >= count(t, c)对于所有 c (证明很简单，就省略了)。

2. 让我们定义firstRight(L)作为最小的R这样一个 [L, R] substring 是一个很好的(可能没有这样的 R )。那么firstRight(L) <= firstRight(L + 1)对于所有有效的 L (因为 1. 和 count(x, y) 函数的属性)。

3. 声明 1. 暗示任何字符串都可以表示为一个向量，其值为 alphabetSize元素，其中 i此向量的第 - 个元素是字符 i 出现的次数.语句 2. 暗示我们可以使用两个指针。

4. 所以这个算法的伪代码是这样的:

   def getCharacterVector(string s):
       result = a vector filled with zeros
       for c in s
           result[c]++
       return result
   
   // Checks that all elements of the first vector
   // are greater than or equal to the corresponding
   // elements of the second vector
   def isGreaterOrEqual(first, second)
       for i = 0 ... length(first)
           if first[i] < second[i]
               return false
       return true
   
   def countSubstrings(string s, string t)
       vT = getCharacterVector(t)
       vS = a vector filled with zeros
       right = 0
       // computes firstRight(0)
       while (right < length(s) and not isGreaterOrEqual(vS, vT))
           vS[s[right]]++
           right++
       if not isGreaterOrEqual(vS, vT) // firstRight(0) is undefined
           return 0 // there are no such substrings
       res = length(s) - right + 1
       for left = 1 ... length(s) - 1
           vS[s[left - 1]]--
           // computes firstRight(left)
           while right < length(s) and vS[s[left - 1]] < vT[s[left - 1]]
               vS[s[right]]++
               right++
           if vS[s[left - 1]] < vT[s[left - 1]] // firstRight(left) is undefined
               break // we are done
            res += length(s) - right + 1
       return res
   

   这里的想法是两个计算从固定位置开始到任何地方结束的好子串的数量，并使用两个指针有效地调整右边界。这个实现的时间复杂度是O(N * ALPHABET_SIZE + M) (这是 O(N + M) 如果我们将字母大小视为常量)，但实际上可以执行 firstRight(0)通过跟踪 vS 中的“坏”位置来提高计算效率和 vT向量并将此向量表示为哈希表以实现 O(N + M)复杂性与字母大小无关。