本周學習內容
- 字串基礎
- 哈希
- KMP
- manecher
字串基礎
String類相關函式
eg.查找給定字串（str）并把相應子串(src)替換為另一給定字串(dest)
int str_replace(string &str, string &src,string &dest)
{
int counter = 0;
int pos = 0;
while ((pos = str.find(src, pos)) != string::npos) {
str.replace(pos, src.size(), dest);
++counter;
pos += dest.size();
}
return counter;//回傳替換的次數
}
哈希
相當于函式中的映射，把字串經過hash后變成一個值，不同字串的hash值基本不會重合，
hash[i] = hash[i - 1] * base + (s[i] - ‘a’);
取字串s[l,r]hash值：
hash[l,r]=f[r]-f[l-1]*p[r-l+1]，
void init(){
p[0]=1;
hash[0] = 0;
int n=strlen(s+1);
for(int i=1;i<=100000;i++)p[i]=p[i-1]*base;
for(int i=1;i<=n;i++)hash[i]=hash[i-1]*base+(s[i]-'a');
}
KMP
雖然看了一晚上博客，但我還是沒理解，然后去某站隨便找了個視頻，發現新大陸（為什么播放量這么低 不合理！）（我不知道把視頻放上來 有興趣的可以搜up主id：代碼隨想錄）先放個板子，代碼來自KMP演算法最淺顯理解——一看就明白
雖然我并沒有一看就明白…
void cal_next(char *str, int *next, int len)
{
next[0] = -1;//next[0]初始化為-1，-1表示不存在相同的最大前綴和最大后綴
int k = -1;//k初始化為-1
for (int q = 1; q <= len-1; q++)
{
while (k > -1 && str[k + 1] != str[q])//如果下一個不同，那么k就變成next[k]，注意next[k]是小于k的，無論k取任何值，
{
k = next[k];//往前回溯
}
if (str[k + 1] == str[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;//這個是把算的k的值（就是相同的最大前綴和最大后綴長）賦給next[q]
}
}
int KMP(char *str, int slen, char *ptr, int plen)
{
int *next = new int[plen];
cal_next(ptr, next, plen);//計算next陣列
int k = -1;
for (int i = 0; i < slen; i++)
{
while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）
k = next[k];//往前回溯
if (ptr[k + 1] == str[i])
k = k + 1;
if (k == plen-1)//說明k移動到ptr的最末端
{
//cout << "在位置" << i-plen+1<< endl;
//k = -1;//重新初始化，尋找下一個
//i = i - plen + 1;//i定位到該位置，外層for回圈i++可以繼續找下一個（這里默認存在兩個匹配字串可以部分重疊）
return i-plen+1;//回傳相應的位置
}
}
return -1;
}
KMP演算法主要用于解決字串匹配的問題，例如求一個文本串中是否出現了模式串，如果用暴力，復雜度是O(m×n)，容易TLE，KMP利用前綴表幫助找到前面已經匹配過的內容，
感覺最難理解的是next陣列的理解，我的理解是next陣列保存了第i位最長相等的前綴和后綴的長度，這里，前綴是包含首字母不包含尾字母的所有子串，后綴就是包含尾字母不包含首字母的所有子串，
例如aabaaf
對于a，匹配的長度為0
對于aa，匹配的長度為1
對于aab，匹配的長度為0
對于aaba，匹配的長度為1
對于aabaa，匹配的長度為2
對于aabaaf，匹配的長度為0
那么得到一個{0,1,0,1,2,0}的陣列就是所需要的前綴表，
那么如何利用這個前綴表進行匹配呢？
假設文本串str為aabaabaaf
模式串ptr為aabaaf
一開始，用str[i]和ptr[i]比對，相等就繼續下一輪匹配，在i=5（i從0開始）發現’b’和’f’不相同，此時找到’f’前面的子串的最長相等前后綴是多少，根據前綴表{0,1,0,1,2,0}可以得到長度為2，因為’aa’的后綴不匹配了，所以找到與其相等的前綴’aa’的后面繼續開始匹配，也就是跳到下標為2的位置’b’繼續匹配，也就是str[5]和ptr[2]開始繼續匹配，
語言five不大會用文字說明，本來想用畫圖說明沒想到還手殘…只能這么描述一下了，將就看看叭，
manecher
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/209052.html
標籤：其他