题意

长度为nnn的字符串中，有多少个子串为niuniu

其中 n≤105n\leq 10^{5}n≤105

对结果模1e9+71e9+71e9+7

算法

深度搜索

dfs(stringidx,niuniuidx)

深度搜索函数，接受当前搜索到的字符串的长度的下标，和niuniu当前匹配到的下标

每次从string的当前位置遍历i in range(stringidx,n)到字符串尾部，如果和要匹配的niuniu 的 下标字符一致，那么递归dfs(i+1,niuniuidx+1)dfs(i+1,niuniuidx+1)dfs(i+1,niuniuidx+1)

代码

class Solution:
    s = ""
    # 递归搜索， 字符串搜索的下标， niuniu匹配的下标
    def dfs(self, stringidx, niuniuidx):
        if niuniuidx == 6: # 完全匹配则返回1 否则返回0
            return 1;
        if stringidx == len(self.s):
            return 0;
        cnt = 0 # 统计方案数
        for i in range(stringidx, len(self.s)): # 从字符串下标向后搜索 尝试匹配 niuniu下标当前位置的字符
            if "niuniu"[niuniuidx] == self.s[i]:
                cnt += self.dfs(i+1,niuniuidx+1) # 如果匹配，递归尝试下一个位置
        return cnt
    def solve(self , s ):
        self.s = s
        return self.dfs(0,0) % 1000000007

复杂度分析

时间复杂度: 我们每一层遍历字符串，都需要O(n)O(n)O(n), 一共6层，所以总复杂度为 O(n6)O(n^6)O(n6) 无法在要求时间内完成

空间复杂度: 我们的空间消耗在递归的内存上，因此和递归的深度相关，注意到递归的深度受到niuniuidx控制，最大为6，所以空间复杂度为O(1)O(1)O(1)

遍历递推

假设题目不是要求子串，而是连续的，那么枚举每一个位置，检查从这个位置开始是不是"niuniu" 即可

但是这里要是子串，也就是来源的字符可能处于不连续的位置，那么我们考虑 逐个匹配"niuniu" 字符串，记录到当前位置，匹配到每一位的分别有多少种方案

stateCnt[i] 表示已经匹了iii个字符的方案数

那么 如果 当前位置是的字符是 'n' 则 stateCnt[1]+=stateCnt[0]stateCnt[1] += stateCnt[0]stateCnt[1]+=stateCnt[0],stateCnt[4]+=stateCnt[3]stateCnt[4]+=stateCnt[3]stateCnt[4]+=stateCnt[3], 也就是原来匹配0个(未匹配任何字符)和匹配了3个(匹配了'niu')的，现在多匹配了一个牛

以 样例 为例

stateCnt 默认状态 n i u n i n i u
0 1 1 1 1 1 1 1 1 1
1(n) 0 0+1=1 1 1 1+1=2 2 2+1=3 3 3
2(n i) 0 0 0+1=1 1 1 1+2=3 3 3+3=6 6
3(ni u) 0 0 0 0+1=1 1 1 1 1 1+6=7
4(niu n) 0 0+0=0 0 0 0+1=1 1 1+1=2 2 2+1=3
5(niun i) 0 0 0+0=0 0 0 0+1=1 1 1+2=3 3+2=5
6(niuni u) 0 0 0 0+0=0 0 0 0 0 0+3=3 (返回值)

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param s string字符串 
     * @return int整型
     */
    int solve(string s) {
        const int mod = 1000000007;
        vector<int> stateCnt = {1,0,0,0,0,0,0}; // 匹配的状态分别是 匹配0个1个2个3个4个5个6个 对应的方案数
        int n = s.length();
        for(int i=0;i<n;i++){
            if(s[i] == 'n'){ // 匹配到n的状态计数转移
                (stateCnt[1]+=stateCnt[0])%=mod;
                (stateCnt[4]+=stateCnt[3])%=mod;
            }else if(s[i] == 'i'){ // 匹配到i的状态计数转移
                (stateCnt[2]+=stateCnt[1])%=mod;
                (stateCnt[5]+=stateCnt[4])%=mod;
            }else if(s[i] == 'u'){ // 匹配到u的状态计数转移
                (stateCnt[3]+=stateCnt[2])%=mod;
                (stateCnt[6]+=stateCnt[5])%=mod;
            }
        }
        return stateCnt[6];
    }
};

复杂度分析

时间复杂度: 我们遍历字符串每一位，每次状态常数代价转移，所以总复杂度为 O(n)O(n)O(n)

空间复杂度: 除了临时变量，我们只用了一个常数大小的state数组来记录，遍历过程中的方案数，空间复杂度为 O(1)O(1)O(1)

知识点

  1. 遍历递推, 我们在递推过程中，表达式为stateCnt[状态]=方法数stateCnt[状态] = 方法数stateCnt[状态]=方法数