c++ - 如何有效地找到具有相同第一个和最后一个字符的字符串中的子字符串数？

Question

我正在尝试查找具有相同第一个和最后一个字符的字符串中的子字符串数。

我可以通过两个 for 循环以天真的方式解决它。

我觉得它可以更有效地解决。

如何以更有效的方式解决它？

Answer 1

遍历字符串，计算每个不同字符出现的次数。那么，如果一个字符只出现一次，则没有以它结尾和开头的子串，如果出现两次——只有1次，如果出现3次——有3次，如果出现4次——6。函数为C( n,2) = n!/(2!(n-2)!) = n(n-1)/2。

这是一个潜在的实现。

inline int Nchoose2(int n) {
  return n*(n-1)/2;
}

std::string s;
std::map<char,int> m;
int cnt = 0;

for (char c : s) {
  if (!m.count(c)) m[c] = 0;
  else ++m[c];
}

for (auto &c : m)
   cnt += Nchoose2(c.second);