題目大意就是將一個字符串分成長度為N的字串。且不同的字符不會超過NC個。問總共有多少個不同的子串。
采用的辦法就是以nc作為進制，把一個子串化為這個進制下的數，再用哈希判斷。由于題目說長度不會超過16，000，000? 所以哈希長度就設為16000000就行。另外為每一個字符對應一個整數，來方便轉化。
?
#include <iostream> #include <cstring> #include <cstdio> #include <cmath>using namespace std;const int maxn=1600000;int n,nc; bool c[20000000]; char s[maxn]; int Hash[256];int main() {ios::sync_with_stdio(false);cin.tie(0);while(cin>>n>>nc){cin>>s;memset(c,false,sizeof(c));memset(Hash,0,sizeof(Hash));int len=strlen(s);int tmp;int cnt=0;for(int i=0;i<len;i++){if(Hash[s[i]]==0){Hash[s[i]]=cnt++;}}int ans=0;for(int i=0;i+n<=len;i++){tmp=0;for(int j=i;j<i+n;j++){tmp*=nc;tmp+=Hash[s[j]];}if(!c[tmp]){ans++;c[tmp]=true;}}cout<<ans<<endl;}return 0; }
poj1741，?
