526互联

【11月LeetCode组队打卡】Task2--String & StringMatch

发布时间 2023-11-18 17:08:21作者: Wennz-y

在CSP里面好多道“水题“基本都离不开字符串/数组的模拟

滚动哈希，字典树，DP几个强强联合基本可以横扫所有难度的字符串算法了，所以在这个task里会好好消化其中前二

字符串和数组有很多相似之处，比如同样使用下标的方式来访问单个字符。根据字符串的特点，将字符串问题分为以下几种：

  • 字符串匹配问题
  • 子串相关问题
  • 前缀 / 后缀相关问题
  • 回文串相关问题
  • 子序列相关问题

关于字符串的字符编码：

  • ASCII（英语为主的语言）

  • Unicode（多语言，其中最常用的就是UTF-8编码）。UTF-8：将Unicode字符根据大小编成1-6个字节，英文1个字节，汉字通常是3个字节。

字符串匹配问题（模式匹配,，Pattern Matching) ：

  • 单模式串匹配：从文本串中找到特定串的所有出现位置。这次主要训练了KMP算法（基于前缀搜索方法）。

  • 多模式串匹配：文本串中找模式串P，其中P是模式串p的集合，找到集合P中p的所有出现位置。

基操

125.验证回文串

测试用例：

a man,a plAn,a canal:Panama

< cctype >

isalnum( )：bool型，判断是否为有效字符（十进制数字/字母

tolower()：char型，将有效字符转为小写字母（toupper

AC:对撞指针--left&right

#include<iostream>
#include<string>
using namespace std;

bool ValidPalindrome(string &s){
    string sgood;
    for(char c:s){
        if(isalnum(c)){
            sgood+=tolower(c);
        }
    }
    int n=sgood.size();
    for(int left=0,right=n-1;left<right;){
        if(sgood[left]!=sgood[right])
            return false;//不是回文串
        ++left;
        --right;
    }
    return true; 
}

int main(){
    string s;
    cin>>s;
    if(ValidPalindrome(s))
        cout<<"true"<<endl;
    else   cout<<"false"<<endl;
    return 0;
}

344.反转字符串

UNAC：翻转字符串角标的关系 i&n-1-i ( ≠ i&n-i )

string ReverseString(string &s){
    int n=s.size();
    for(int i=0;i<=n/2;++i){
        swap(s[i],s[n-i]);//s[n-1-i]
    }
    return s;
}

AC：双指针--left&right

n&n-1-i 无法替代lr指针（for循环判断不会出错

#include<iostream>
#include<string>
using namespace std;
string reverse(string &s){
    int left=0;
    int right=s.size()-1-left;
    for(;left<right;++left,--right){
        swap(s[left],s[right]);
    }
    cout<<s<<endl;
    return s;
}

int main(){
    string s;
    cin>>s;
    reverse(s);
    cout<<"[\"";
    for(int i=0;i<s.size()-1;i++){
        cout<<s[i]<<"\",\"";
    }
    cout<<s[s.size()-1]<<"\"]";
}

557.翻转字符串中的单词III

AC：使用额外空间

#include<iostream>
#include<string>
using namespace std;

string reverse(string &s){
    string word;//开新串存翻转后字符串
    int n=s.size();
    int i=0;
    while(i<n){
        int start=i;//单词的起始下标
        while(i<n&&s[i]!=' '){//始
            i++;
        }
        for(int p=start;p<i;p++){
            word.push_back(s[start+i-1-p]);//翻转后存入
        }
        while(i<n&&s[i]==' '){//终
            i++;
            word.push_back(' ');
        }
        return word;
    }
}

int main(){
    string s,rev;
    cin>>s;
    rev=reverse(s);
    cout<<rev;
    return 0;
}

字符串单模式匹配

BruteForce算法

BF暴力匹配：双层for循环

  • 成功：i++; j++;

  • 失败：i回溯；j置0；

RabinKarp算法（滚动哈希算法

RK，使用哈希函数在文本中搜索

。。。看官方讲解的时候只能说什么依托答辩，一堆高级名词直接劝退，后来找到一篇CSDN直呼牛蛙

（参考：滚动哈希——干脆叫前缀和得了——CSDN)

KMP算法

（参考：题解：多图预警??详解 KMP 算法——力扣)

KMP算法：

  • 成功：i++; j++;

  • 失败：i不变；j = next[ j ] ;

  • 核心：前缀函数--前缀表

区分一下前后缀和真前后缀（刚开始学的时候很容易迷糊：

  • 真前缀：去尾，从前往后逐字增一

  • 真后缀：去首，从后往前逐字增一，字符之间相对顺序不变；亦即，不包含第一个字符的所有以最后一个字符结尾的连续子串

  • 举个栗子：字符串"initialize"

所有真前缀：i   in   ini   init   initi   initia   initial   initaili   initializ

所有真后缀：e  ze  ize   lize   alize   ialize   tialize   itialize   nitialize

单个字符：存在前后缀，就是其本身，但不存在真前后缀，规定为0

会用到三个数组：

  • 文本串T

  • 模式串p

  • 前缀表next：在不p包含尾字符的前缀字符全排列中，每种排列的最长相等前后缀数组成的表。

  • 因取失配字符上一个字符的前缀表值用：指示回退下标，所以叫做next。（与prefix用法相同，都是前缀表）

算法实现：

//在背模板了，别急

28.找出字符串中第一个匹配项的下标

AC1：BF

int STRBF(string &haystack,string &needle){
    int n=haystack.size(),m=needle.size();
    for(int i=0;i+m<=n;i++){ //i<n, nonono
        bool flag=true;
        for(int j=0;j<m;j++){
            if(haystack[i+j]!=needle[j]){
                flag=false;
                break;
            }
        }
        //每一次p串匹配完都判断一次flag
        if(flag){
            return i;
        }
    }
    return -1;
}

AC2：KMP

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//KMP：next array
int STRKMP(string &haystack,string &needle){
    int m=haystack.size(),n=needle.size();
    if(n==0) 
        return 0;
    vector<int> next(n);
    //l找前缀, r找后缀
    for(int l=0,r=1;r<n;r++){
        while (l>0 && needle[l]!=needle[r])
            l=next[l-1];
        if(needle[l]==needle[r])
            l++;
        next[r]=l;
    }
    for(int i=0,j=0;i<m;i++){
        while(j>0 && haystack[i]!=needle[j])
            j=next[j-1];
        if(haystack[i]==needle[j])
            j++;
        if(j==n)
            return i-n+1;
    }
    return -1;
}

int main(){
    string haystack,needle;
    cin>>haystack;
    cin>>needle;
    int ans=0;
    ans=STRKMP(haystack,needle);
    cout<<ans;

    return 0;
}

796.旋转字符串

< string > -- substr

字符串截取函数

（日常调库的一天

string s,a,b,c;
s="123a bc";
a=s.substr(0,3);//123，从第一位开始往后截取3个字符
b=s.substr(1,4);//123a，从第一位开始往后截取4个字符
c=s.substr(4,3);//a b，从第四位开始往后截取3个字符

AC1：调库

bool rotateSubStr(string &s,string &goal){
    int n = s.size();
    string str;
    for(int i = 1; i < n; ++i) {
        if(s[i] == goal[0]) {
            str = s.substr(i);
            str += s.substr(0, i);
            if(str == goal) {
                return true;
            }
        }
    }
    return false;
}

AC2：暴力模拟

bool rotateStrSmlt(string &s,string &goal){
    int m=s.size(),n=goal.size();
    //长度不匹配，直接判否
    if(m!=n)
        return false;

    for(int i=0;i<n;i++){
        bool flag=true;
        for(int j=0;j<n;j++){
            if(s[(i+j)%n]!=goal[j]){
                flag=false;
                break;
            }
        }
        if ((flag))
            return true;
    }
    return false;
}

AC3：KMP

bool rotateStrKMP(string s, string goal) {
    if(s.size() != goal.size()) return false;

    string res = s + s;
    //next array
    vector<int> ne(goal.size());
    ne[0] = -1;
    for(int i = 1, j = -1; i < goal.size(); i ++)
    {
        while(j != -1 && goal[j + 1] != goal[i]) j = ne[j];
        if(goal[j + 1] == goal[i]) j++;
        ne[i] = j;
    }

    for(int i = 1, j = -1; i < res.size(); i ++)
    {
        while(j != -1 && goal[j + 1] != res[i]) j = ne[j];
        if(goal[j + 1] == res[i]) j ++;
        if(j == goal.size() - 1) return true;
    }

    return false;
}