这个字谜子串搜索算法中的数学

Question

在下面的代码中：

function sherlockAndAnagrams(s) {
var pairs = 0;
var subStrings = {};

//find all substrings of our string, count them in a hash
for(var i = 0; i < s.length; i++){
    for(var j = i; j < s.length; j++){
        let tempSubString = s.substring(i, j+1).split("").sort().join("");
        if(subStrings[tempSubString]){
            subStrings[tempSubString] +=1;
        }else{
            subStrings[tempSubString] = 1;
        }
    }
}

//****ATTENTION******
for(var keys in subStrings){
    if(subStrings[keys] > 1){
    let temp = (subStrings[keys])*(subStrings[keys]-1)/2;
       pairs += temp;
   }
}
return pairs;
}

我不确定这个公式背后的数学是如何工作的：

subString[keys])*(subString[keys]-1)/2

假设 s = "kkkk", "k"s

有 6 个字谜

有人可以解释一下吗？

此外，这也说明我在某些数学方面可能有点欠缺。如果你能给我一个很好的 material 学习来解决这样的数学问题，我将不胜感激！

Answer 1

逻辑如下：您有 n 个单词，它们是彼此的变位词。从那里你可以 select 多少对字谜？这是 (n,2) 的简单 combinatoric question with a known answer: binominal coefficient 即 n*(n-1)/2.

逻辑是，如果计算所有变位词，第一个变位词可以 n 种方式，第二个变位词可以 n-1 种方式，但每个变位词将被考虑两次：一次是 ab=ba，另一次是 ba=ab

这个字谜子串搜索算法中的数学

Math in this anagram substring search algorithm

javascript

algorithm

math

anagram