字符串专题

KMP喜提我狗命

字符串hash初步

/*字符串hash是指将一个字符串S映射为一个整数，使得该整数可以尽可能唯一地代表字符串S。
例如：假设字符串均由大写字母A-Z构成。A-Z表示0-25，二十六进制，构成的最大整数26^len - 1
*/
int hashFunc(char S[], int len) {
	int id = 0;
	for(int i = 0; i < len; i++) {
		id = id * 26 + (S[i] - 'A');
	}
	return id;
}
/*同理，如果字符串中出现了小写字母，那么把A-Z视为0-25，而把a-z作为26-51，五十二进制
*/
int hashFunc(char S[], int len) {
	int id = 0;
	for(int i = 0; i < len; i++) {
		if(S[i] >= 'A' && S[i] <= 'Z') {
			id = id * 52 + (S[i] - 'A');
		}else if(S[i] >= 'a' && S[i] <= 'z') {
			id = id * 52 + (S[i] - 'a') + 26;
		}
	}
	return id;
}
/*如果出现数字
① 按照瞎写字母的方式，增大进制数至62。
② 如果字符串的末尾是数字，那么把前面英文字母部分转换成整数，再将末尾的数字直接拼接上去。例如"BCD4"
*/
int hashFunc(char S[], int len) {
	int id = 0;
	for(int i = 0; i < len - 1; i++) {
		id = id * 26 + (S[i] - 'A');
	}
	id = id * 10 + (S[len - 1] - '0');
}

//question: 给出N个字符串(由恰好三位大写字母组成)，再给出M个查询字符串，问每个查询字符串在N个字符串中出现的次数。

字符串hash进阶

//H[i] = (H[i-1] × p + index(str[i])) % mod
//其中p = 10000019，mod = 1000000007

//questin: 给出N个只有小写字母的字符串，求其中不同的字符串个数。
//solution: 把每个字符串转化成整数，然后去重。(可以用set和map，但比字符串hash慢一点点)unordered_set呢？
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int P = 10000019;
vector<int> ans;

long long hashFunc(string str) {
	long long H = 0;
	for(int i = 0; i <str.size(); i++) {
		H = (H * P + (str[i] - 'a')) % MOD;
	}
	return H;
}
int main() {
	string str;
	while(getline(cin, str), str != "#") {
		long long id = hashFunc(str);
		ans.push_back(id);
	}
	sort(ans.begin(), ans.end());
	int count = 0;
	for(int i = 0; i < ans.size(); i++) {
		if(i == 0 || ans[i] != ans[i-1]) {
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

//question: 输入两个长度均不超过1000的字符串，求他们的最长公共子串的长度。
//solution: 分别对两个字符串的每个子串求出hash值，然后找出两堆子串对应的hash值中相等的那些，便可以找到最大长度。
//T(n) = O(n² + m²)
//变式: 输出最大公共子串本身codeup2432

//question: 最长回文子串
//solution: 字符串hash + 二分
//T(n) = O(nlogn)

KMP 算法

//KMP算法由Knuth、Morris、Pratt共同发现的。

//求解next数组:
void getNext(char s[], int len) {
	next[0] = -1;
	int j = next[0];
	for(int i = 1; i < len; i++) {
		while(j != -1 && s[i] != s[j + 1])
			j = next[j];
		if(s[i] == s[j + 1]) j++;
		next[i] = j;
	}
}

/*算法思想：
① 初始化j = -1，表示pattern当前已被匹配的最后位。
② 让i遍历文本串text，对每个i，执行③④来试图匹配text[i]和pattern[j+1]。
③ 不断令j = next[j]，直到j回退为-1，或是text[i] == pattern[j+1]成立。
④ 如果text[i] == pattern[j+1],则令j++。如果j达到m-1，说明pattern是text的子串，返回true。
*/
bool KMP(char text[], char pattern[]) {
	int n = strlen(text), m = strlen(pattern);
	getNext(pattern, m);
	int j = -1;
	for(int i = 0; i < n; i++) {
		while(j != -1 && text[i] != pattern[j + 1])
			j = next[j];
		if(text[i] == pattern[j + 1]) j++;
		if(j == m - 1) return true;
	}
	return false;
}

//统计模式串pattern出现次数的KMP算法
int KMP(char text[], char pattern[]) {
	int n = strlen(text), m = strlen(pattern);
	getNext(pattern, m);
	int j = -1, ans = 0;
	for(int i = 0; i < n; i++) {
		while(j != -1 && text[i] != pattern[j + 1])
			j = next[j];
		if(text[i] == pattern[j + 1]) j++;
		if(j == m - 1) {
			ans++;
			j = next[j];
		}
	}
	return ans;
}

//优化next数组: nextval[]
void getNextval(char s[], int len) {
	int j = -1;
	netxval[0] = -1;
	for(int i = 1; i < len; i++) {
		while(j != -1 && s[i] != s[j + 1])
			j = nextval[j];
		if(s[i] == s[j + 1]) j++;
		if(j == -1 || s[i + 1] != s[j + 1])
			nextval[i] = j;
		else
			nextval[i] = nextval[j];
	}
}

//从有限自动机的角度看待KMP算法