题解 | #好多牛牛#

好多牛牛

http://www.nowcoder.com/practice/edced5e80f3e46efa9c965e7f634c58c

题意

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

其中 $n\leq 10^{5}$

对结果模 $1 e 9 + 7$

算法

深度搜索

dfs(stringidx,niuniuidx)

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

每次从string的当前位置遍历i in range(stringidx,n)到字符串尾部，如果和要匹配的niuniu 的下标字符一致，那么递归 $d f s (i + 1, n i u n i u i d x + 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)$ , 一共6层，所以总复杂度为 $O (n^{6})$ 无法在要求时间内完成

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

遍历递推

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

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

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

那么如果当前位置是的字符是 'n' 则 $s t a t e C n t [1] + = s t a t e C n t [0]$ , $s t a t e C n t [4] + = s t a t e C n t [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];
    }
};