P7377 题解

· · 题解

题解

暴力解法

这绝对是很容易想到的，字符串的每一位都用一个 n^2 的扫描来找，一共 m 位所以最后时间复杂度为 O(n^2 m)，毫无疑问，它不够优秀。

优秀解法

这个解法的思路可能比较清奇，有一点像哈希。对于每一位字符，我们赋予它一个值，问号特殊处理。也就是说每一个字符串到处理完后都会变成一个数字，这时我们就可以记录下这个数字出现的次数，进而得出答案。显然，map 在这里很合适。

AC code

代码的话还是很好理解的。

#include <cstdio>
#include <unordered_map>
using namespace std;
const int N=50005,M=6;
char s[N][M];
int n,m;
unordered_map<int,int> mp;
void push(char str[],int step,int now){
    if(step==m){
        mp[now]++;
        return;
    }
    int x=now*30; //这里乘的数必须大于 27，避免值交叉 
    if(str[step]!='?'){ //两种处理 
        push(str,step+1,x+str[step]-'a'); //字母就直接加 
        push(str,step+1,x+26); //考虑到同位有问号的情况 
    }
    else
        push(str,step+1,x+27); //这一步考虑到问号本身的值 
}
int query(char str[],int step,int now){
    if(step==m){
        if(!mp.count(now)) return 0;
        return mp[now];
     }
    int sum=0,x=now*30;
    if(str[step]!='?') sum+=query(str,step+1,x+str[step]-'a'); //字母直接加 
    else sum+=query(str,step+1,x+26); //问号就跳过 
    sum+=query(str,step+1,x+27); //这一步要写在外面，避免漏掉这一位是问号的情况 
    return sum;
}
int main(){
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=0;i<n;++i){
        scanf("%s",s[i]);
        ans+=query(s[i],0,0);
        push(s[i],0,0);
    }
    printf("%d",ans);
    return 0;
}