解题思路:
(1)字符串的最大长度是6,可以用哈希表来做,最大为26^6=308915776(可以开map做)
(2)求的是别的字符串跟指定字符串之间的价值和,所以价值和=总价值-字符串本身包含的价值
a:1
b:2
c:3
~
y:25
z:26
aa:126+1=27
ab:126+2=28
ac:126+3=29
~
az:126+26=52
~~
zz:2626+26
aaa:12626+126+1
~
一开始将所有的价值都储存一遍(用map存储,放在第一个map:v里面)
第二次查找的时候,只要用v里面的数据-自己本身的价值,最后全部加起来就是最后的结果了。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; int n,k,m; map<int,int>v,now; string s[500010]; int main() { cin >> n >> k; for(int i=1;i<=n;i++) //对第i个字符串进行初始化,从(0,0),(0,1),(0,2),(0,3)~~~一直到(len-1,len-1) { cin >> s[i]; for(int l=0;l<k;l++) { int z=0; for(int r=l;r<k;r++) { z *= 26; z += s[i][r]-'a'+1; //将第i个字符串的第r个字符转化成(1~26)形式 v[z] += r-l+1; //+ 1*长度 } } } cin >> m; while(m--) { int x,len; cin >> x >> len; now.clear(); int ans=0; for(int l=0;l<k;l++) { int z=0; for(int r=l;r<k;r++) { z*=26; z += s[x][r]-'a'+1; now[z] += r-l+1; } } for(int l=0;l<k;l++) { int z=0; if( l+len > k) continue; //超出了最大长度k,直接continue就可以了 for(int r=l ; r<min(l+len,k) ; r++) { z*=26; z += s[x][r]-'a'+1; } ans += v[z]-now[z]; //减掉自己本身的价值 } cout << ans << endl; } }