点击打开题目链接
题意就是，给出一个字符串，里面有NC个不同字符，求其中长度为n的不同子字符串个数
差不多就是字符串的哈希算法的一道简单应用题了，《挑战程序设计竞赛》书上第373页开始有相关内容
其中，假设字符串C=c1c2...cm，选取两个合适的互素常数b和h，可定义哈希函数
H(c)=(c1*b^(m-1)+c2*b^(m-2)+c2*b^(m-3)+...+cm*b^0) mod h
其中b是基数，相当于把字符串看作b进制数。这样，字符串S=s1s2...sn从位置k+1开始长度为m的字符串子串
S[k+1...k+m]的哈希值，就可以从位置k开始的字符串子串S[k...k+m-1]的哈希值，直接进行如下计算。
H(S[k+1...k+m])=(H(S[k...k+m-1])*b-sk*b^m+sk+m) mod h
这道题里，转换下，len-n+1个子字符串对应len-n+1个哈希值，求不同子字符串个数就相当于求不同哈希值个数
其他的，再利用Java带的数据结构套套，即可解决，代码如下：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.Reader; import java.util.HashMap; import java.util.HashSet; import java.util.StringTokenizer; public class Main { /** * @param args */ static long nnum, val, value; static int n, nc, cnt; static BufferedReader reader; static StringTokenizer tokenizer; static String str, str2; static char ch[]; static HashSet<Integer> hashSet; static HashMap<Character, Integer> hashMap; static long monum = Integer.MAX_VALUE; static long mulnum = 100000007; static long num[]; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub reader = new BufferedReader(new InputStreamReader(System.in)); tokenizer = new StringTokenizer(""); str2 = reader.readLine(); tokenizer = new StringTokenizer(str2); n = Integer.parseInt(tokenizer.nextToken()); nc = Integer.parseInt(tokenizer.nextToken()); str = reader.readLine(); ch = str.toCharArray(); hashSet = new HashSet<Integer>(); num = new long[ch.length]; hashMap = new HashMap<Character, Integer>(); if (n > ch.length) System.out.println(0); else { value = 1; for (int i = 0; i < n; i++) { if (!(hashMap.containsKey(ch[i]))) { cnt++; hashMap.put(ch[i], cnt); num[i] = cnt; } else num[i] = hashMap.get(ch[i]); val = (val * mulnum + num[i]) % monum; value = (value * mulnum) % monum; } hashSet.add((int) val); for (int i = n; i < ch.length; i++) { if (!(hashMap.containsKey(ch[i]))) { cnt++; hashMap.put(ch[i], cnt); num[i] = cnt; } else num[i] = hashMap.get(ch[i]); val = (val * mulnum + num[i]) % monum; val = ((val - value * num[i - n]) % monum + monum) % monum; hashSet.add((int) val); } System.out.println(hashSet.size()); } } }
