首页 > 代码库 > Poj1200题解

Poj1200题解

2024-07-24 06:04:32   218人阅读

题意：给定模式字串长度和不同字符的个数，求一个长字符串的不同子串的个数

分析：刚开始做这个题目的时候，本来是想直接用HashSet做的，但是觉得一是不太可能这么水，二是可能空间也不一定够，所以就想啊想，想偏了。后来在discuss里面看到有直接用HashMap等水过的，我就试了试，还真能过。不过这种做法效率不高，实现也不难，所以就不说了。

　　另一种真正用上所有条件的方法就是Rabin-Karp算法做。通过将不同的字符表示成以d为进制数的d个数字，将每一个字符串表示成一个多位d进制的数t，对比不同字符串所产生的的t来判断两个字符串是否相等。同时在本题中也可以将t用于计算得出的hash的key值。下面是代码和注释

 1 import java.io.BufferedReader; 2 import java.io.IOException; 3 import java.io.InputStreamReader; 4  5 public class Poj1200 { 6  7     public static void main(String[] args) throws IOException { 8         // TODO Auto-generated method stub 9 10         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));11         String[] strArgs = br.readLine().split(" ");12         13         boolean[] hash = new boolean[16000000];14         15         int N = Integer.parseInt(strArgs[0]);16         int NC = Integer.parseInt(strArgs[1]);17         18         int[] charToInt = new int[260];//保留一个字节，八位的空间0-256表示ansii码的值19     20         int seed = 0;21         String text = br.readLine();22     23         for(int i = 0;i<text.length();i++)24         {25             if(charToInt[text.charAt(i)]==0)26             {27                 charToInt[text.charAt(i)] = seed++;//对每个新出现的字符赋予数字表示28             };29         }30         31         int index = 0;32         int temp =0;33         int t = 1;34         for(int i = 0;i<N;i++)35         {36             temp = temp * NC + charToInt[text.charAt(i)];//计算第一个N位的字符串的NC精制数字表示37             t *= NC;//38         }39         if(!hash[temp])40         {41             hash[temp] = true;42             index++;43         }44         45         int ilength = text.length()-N;46         for(int i = 1;i<=ilength;i++)47         {48             temp = (temp*NC + charToInt[text.charAt( i + N-1)])%t;//去除temp的最高位，补上新偏移到的最低位49             if(!hash[temp])50             {51                 hash[temp] = true;52                 index++;53             }54         }55         System.out.println(index);56     }57 58 }

 

Poj1200题解


联系
我们