大数据算法系列9:字符串匹配问题，海量字符串处理

一. 字符串匹配

1.1 字符串匹配

字符串匹配:
字符串匹配在实际工作中经常遇到，但是我们经常使用的是编程语言自带的功能，对底层了解不多。

1.2 字符串匹配算法

1.2.1 朴素算法

这个就很简单的逻辑了，按照顺序挨个去进行比对，如果第一个相同，就对比第二个，依次类推。

1.2.2 Rabin-Karp算法

类似求和取余，如果余数相同，再挨个比较一次，性能会优于朴素算法。

1.2.3 字符串匹配自动机

二. 练习题

2.1 面试题(第一个只出现一次的字符)

题目:

分析:
将每个字母出现的次数存入哈希表，然后在遍历哈希表找只出现一次的字母即可。

代码:

class Solution {
    public char firstUniqChar(String s) {
        //定义哈希集合存储字符和出现数次
        HashMap<Character, Integer> map = new HashMap<>();
        //遍历字符串记录次数
        for(char c: s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        //寻找只出现一次的字符
        for(char c: s.toCharArray()){
            if(map.get(c) == 1){
                return c;
            }
        }
        return ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2 POJ1200(字符串hash)

大意:
给定一个字符串，其中含有不同的字母数量为m，现在求这个字符串中有多少个长度为n且长的互不相同的字符子串 。举个例子, n=3, m=4 ，字符串 “daababac”. 长度为3的不同的子串分别是: “daa”; “aab”; “aba”; “bab”; “bac”. 因此, 答案是5.用set会超时。

分析:
把 三个的字符串存储set即可，不过既然会超过时间，那么就转化为对应的数值即可。

代码:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main
{
	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		String str = scan.next();
		Set fuck = new HashSet();
		int len = str.length();
		for (int i = 0; i < len-N+1; i++) 
		{
			String tem = str.substring(i,i+N);
			fuck.add(tem);
		}
		System.out.println(fuck.size());
	}
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.3 Uva10006(Carmichael Number)

题目:

分析:
首先判断 n 是不是素数，如果不是素数再 遍历 1~n 之间的数，求出每一个 $x^n$，看是不是满足条件，对于 xⁿ 可以使用书上讲的反复平方法进行快速幂运算。

代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
 
public class Main {
	
	private static long mod_pow(long x, long n, long mod){
		//快速幂
		//求x的n次方模mod
		if(n == 0) return 1;
		long res = mod_pow(x*x%mod, n/2, mod);
		if((n&1) > 0) res = res*x%mod;
		return res;
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while(in.nextToken() != StreamTokenizer.TT_EOF){
			int n = (int)in.nval;
			if(n == 0) break;
			boolean flag = false;
			for(int i = 2; i<=Math.sqrt(n); i++){
				if(n % i == 0){
					flag=true;
					break;
				}
			}
			if(n == 2) flag=false;
			if(flag){
				for(int i = 2; i<n; i++){
					if(mod_pow(i, n, n)%n != i){
						flag = false;
						break;
					}
				}
			}
			if(flag){
				out.println("The number "+n+" is a Carmichael number.");
			}
			else out.println(n+" is normal.");
			out.flush();
			
		}
		
		
		
		
	}
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

参考:

1. http://www.dataguru.cn/article-5747-1.html