P8630 [蓝桥杯 2015 国 B] 密文搜索 题解

· · 题解

题目在这里。

先看题

题意就是看那 n 行密码，然后在原字符串中找一个 8 个字符的区间，使得密码中的字符调换顺序之后与区间一模一样。求有多少个这样的区间。

思路

双重循环进行枚举，外层枚举密码，内层枚举原字符串的区间范围。分别统计一下区间中和密码中 24 个小写字母的数量，如果匹配，则答案加一。

时间复杂度

定义 \lvert s\rvert 为字符串 s 的长度,则时间复杂度为：

O(n\lvert s\rvert)

代码

#include <iostream>
#include <string>
using namespace std;
#define int long long
#pragma G++ optimize(2)
int n,ans;
string s,a[1005];//s是原字符串，a存密码
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //读入
    cin>>s>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    for(int i=1; i<=n; i++) {//枚举密码
        for(int j=0; j+7<s.length(); j++) {//枚举区间
            int v[200]={},v2[200]={};
            //统计密码
            v[(int)a[i][0]]++;
            v[(int)a[i][1]]++;
            v[(int)a[i][2]]++;
            v[(int)a[i][3]]++;
            v[(int)a[i][4]]++;
            v[(int)a[i][5]]++;
            v[(int)a[i][6]]++;
            v[(int)a[i][7]]++;
            //统计区间
            v2[(int)s[j]]++;
            v2[(int)s[j+1]]++;
            v2[(int)s[j+2]]++;
            v2[(int)s[j+3]]++;
            v2[(int)s[j+4]]++;
            v2[(int)s[j+5]]++;
            v2[(int)s[j+6]]++;
            v2[(int)s[j+7]]++;
            //26个字母全相同的情况下
            if(v['a']==v2['a']&&v['b']==v2['b']&&v['c']==v2['c']&&v['d']==v2['d']&&v['e']==v2['e']&&v['f']==v2['f']&&v['g']==v2['g']&&v['h']==v2['h']&&v['i']==v2['i']&&v['j']==v2['j']&&v['k']==v2['k']&&v['l']==v2['l']&&v['m']==v2['m']&&v['n']==v2['n']&&v['o']==v2['o']&&v['p']==v2['p']&&v['q']==v2['q']&&v['r']==v2['r']&&v['s']==v2['s']&&v['t']==v2['t']&&v['u']==v2['u']&&v['v']==v2['v']&&v['w']==v2['w']&&v['x']==v2['x']&&v['y']==v2['y']&&v['z']==v2['z']){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}