String__

Catalog

One 、 String hash

（1）BKDRHash

Two 、 The longest substring without repetition

3、 ... and 、 Dictionary tree

Four 、KMP Algorithm  

---

One 、 String hash

         Hash each string with a hash function , Map to different numbers , That is, a complete integer hash value ,（ Hash function can be understood as , Pass in something , Come up with an integer .） Then you can find the string according to the hash value , Next, use data structures or STL Complete weight judgment 、 Statistics 、 Query and so on .

        Hash function is the core . Theoretically , Any one h(x) Can be hash function , However, a good hash function should try to avoid conflicts .

        perfect hash function It refers to the hash function without conflict . There are some classic hash functions , for example BKDRHash、APHash、DJBHash、JSHash etc. . In general use BKDRHash, The hash value obtained will hardly collide .

（1）BKDRHash

BKDRHash namely Hexadecimal hash , Convert string to 1 A specific hexadecimal number .

#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char ch[1505]{};
ull a[10005]{};
const int base = 233;
//  Think of this string as base Binary number , Turn it into 10 Binary number .
ull Hash(char ch[]) {
	ull ans = 0;
	int len = strlen(ch) - 1;
    // Converts a string to  base Base number   Number of numbers 
    // If the data is too large ,ull Provide automatic overflow function 
	for (int i = 0; i <= len; ++i) {
		ans = ans * base + (ull)ch[i];
	}
	return ans;
}
int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%s", ch);
		a[i] = Hash(ch);
	}
	sort(a + 1, a + 1 + n);
    // The first string must not have been repeated 
	int ans = 1;
    // The first one is compared with the second one    The center of gravity here is in the second .
	for (int i = 1; i <= n - 1; ++i) {
		if (a[i] != a[i + 1])ans++;
	}
	cout << ans << endl;
	return 0;
}

Two 、 The longest substring without repetition

Draw out with an example ：

Example  1:

 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

Example 2:

Input : s = "pwwkew"
Output : 3
explain : Because the longest substring without repeating characters is  "wke", So its length is 3.
          Please note that , Your answer must be Substring The length of ,"pwke"  Is a subsequence , Not substring .

The solution has several characteristics ：

1. If A Characters appear , that A The string before the character should be discarded

  namely start=last[index]+1;    The beginning becomes the position where the last character appears plus 1;

2. The longest length is directly used i-start+1 （ The distance between two characters ） Calculation is enough .

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[256];
        memset(last,-1,sizeof(last));
        int start=0;
        int rel=0;
        int n=s.size()-1;
        for(int i=0;i<=n;++i){
            //index  Is the character 
            int index=s[i];
            start=max(start,last[index]+1);
            rel=max(rel,i-start+1);
            last[index]=i;
        }
        return rel;
    }
};

3、 ... and 、 Dictionary tree

First, we use the normal dictionary tree to realize , The code is clear , But the requirements for space are high . Better 、 A more compact storage method is to use an array to realize the data structure of the dictionary tree .

 

//  Dictionary tree  /  Word search tree  trie
#include<bits/stdc++.h>
using namespace std;
//  Definition of dictionary tree 
struct Trie{
    Trie *next[26];
    //  Yes num Prefix of a string   From the root to this character .
    int num;
    //  Constructors 
    Trie(){
        for (int i = 0; i < 26;++i){
            next[i] = NULL;
        }
        num = 0;
    }
};
Trie root;
void insert(char str[]){
    Trie *p = &root;
    for (int i = 0; str[i];++i){
        if(p->next[str[i]-'a']==NULL){
            p->next[str[i] - 'a'] = new Trie;
        }
        p = p->next[str[i] - 'a'];
        p->num++;
    }
}

int Find(char str[]){
    Trie *p = &root;
    for (int i = 0; str[i];++i){
        if(p->next[str[i]-'a']==NULL){
            return 0;
        }
        p = p->next[str[i] - 'a'];
    }
    return p->num;
}
int main(){
    char str[11];
    while(gets(str)){
        if (!strlen(str)){
            break;
        }
        insert(str);
    }
    while(gets(str)){
        cout << Find(str) << endl;
    }
    system("pause");
    return 0;
}

  Using array to realize dictionary tree

const int MAX = 1e6 + 5;
int trie[MAX][26]; //  Used to store location 
int num[MAX];
int pos = 1; //  Current newly allocated storage location   From 1 A place to start 
void insert(char str[]){
    int p = 0;  // p :  Search from the root , Indicates the currently searched location 
    for (int i = 0; str[i];++i){
        int n = str[i] - 'a';
        if(trie[p][n]==0){
            trie[p][n] = pos++;
        }
        p = trie[p][n];
        num[p]++;
    }
}
int Find(char str[]){
    int p = 0;
    for (int i = 0; str[i];++i){
        int n = str[i] - 'a';
        if(trie[p][n]==0){
            return 0;
        }
        p = trie[p][n];
    }
    return num[p];
}

Four 、KMP Algorithm  

KMP Algorithm Video Explanation https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=14794319765921941518&spm_id_from=333.337.0.0https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=14794319765921941518&spm_id_from=333.337.0.0 Here is a recommended explanation KMP In the video （ Bloggers think up Lord tql ）

#include<bits/stdc++.h>
using namespace std;
int Next[505];
void getFail(char str[], int len){
    Next[1] = 0;
    int i = 1, j = 0;
    while(i<=len){
        if(j==0||str[i] == str[j]){
            Next[++i] = ++j;
        }
        else{
            j = Next[j];
        }
    }
}
int main(){
    cout << "last example : ababacm " << endl;
    char ch[505];
    scanf("%s", ch + 1);
    int len = strlen(ch + 1);
    getFail(ch, len);
    for (int i = 1; i <= len; ++i){
        cout << Next[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}