Equal Sentences题解

题意:
给一个字符串 S ，求与其相似的字符串 T 的个数：

相似的定义：

1.两个字符串单词的个数相同。

2.对于一个词 a ，它在字符串 S 中的第 i 次出现和在 字符串T 中的第 i 次出现的指数相差不超过1。
思路:
如果 a[i]==a[i−1] ，a[i] 和 a[i−1] 不必交换,那么 f[i]=f[i−1] 。

如果 a[i]!=a[i−1] ，那么 f[i]=f[i−1]+f[i−2] 。f[i-1]继承前面相似情况个数,f[n-2]代表交换a[i]与a[i-1]后前面相似情况个数.

#include<iostream>
#include<string>
using namespace std;

const int N = 100005, mod = 1e9 + 7;
int f[N], n;// f[i] 为前 i 个单词所组成的字符串的相似但本质不同的字符串的个数
string s[N];
int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> s[i];
    }
    fill(f, f + n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] = f[i - 1];
        if (i >= 2 && s[i] != s[i - 1]) {
            f[i] = (f[i] + f[i - 2]) % mod;
        }
    }
    cout<<f[n]<<endl;
    }
    return 0;
}