• 字符串c++练习（KMP等）

    反转字符串

    文章目录


    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 

    不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    class Solution {
public:
    void reverseString(vector<char>& s) {
    //    int i=0;
    //    int j=s.size()-1;
    //    while(i
    //        swap(s[i],s[j]);
    //        i++;
    //        j--;
    //    }
    reverse(s.begin(),s.end());
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    反转字符串||

    给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

    • 1
    • 2
    • 3
    • 4
    示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

    • 1
    • 2
    • 3
    • 4
    class Solution {
public:
    string reverseStr(string s, int k) {
    //     for(int i = 0; i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    替换空格

    请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."

    • 1
    • 2
    • 3
    • 4
    class Solution {
public:
    string replaceSpace(string s) {
        // int count = 0 ;
        // int OldSize = s.size();
        // for (int i = 0; i< s.size();i++) {
        //     if(s[i]==' ') {
        //         count++;
        //     }
        // }
        // //扩充字符串s的大小，也就是每个空格替换成“%20”之后的大小
        // s.resize(s.size()+count*2);
        // int NewSize = s.size();
        // //从后先前将空格替换为"%20" 
        // int j = OldSize-1;
        // int i = NewSize-1;
        // while(j
    • 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

    翻转字符串里的单词

    给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    class Solution {
public:
    string reverseWords(string s) {
    //     //O(n)
    // reverse(s.begin(),s.end());
    // int n = s.size();
    // int idx = 0;
    // for ( int start = 0;start < n;start++) {
    //     if(s[start]!=' '){
    //         // 填一个空白字符然后将idx移动到下一个单词的开头位置
    //         if(idx != 0) {
    //             s[idx++]=' ';
    //         }
    //         // 循环遍历至单词的末尾
    //         int end = start;
    //         while(end d;
    string word;
    while(left<=right) {
        char c = s[left];
        //添加单词到队列里
        if(word.size() && c==' ') {
            d.push_front(move(word));
            word="";
        }
        //一个一个字母添加
        else if(c!=' ') {
            word+=c;
        }
        ++left;
    }
    //添加最后一个单词
    d.push_front(move(word));
    string ans;
    //判断单词，拿一个单词添加一个空格
    while(!d.empty()) {
        ans+=d.front();
        d.pop_front();
        if(!d.empty())
        ans+=' ';
    }
    return ans;

    }
};


    • 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
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    左旋转字符串

    字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

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

    给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    class Solution {
public:
    // void getNext(int* next, const string& s){
    //    int j = -1;
    //    next[0]=j;
    //     for(int i = 1; i=0&&s[i]!=s[j+1]) { //前后缀不相同
    //             j=next[j];  //向前后退
    //           }
    //         if(s[i]==s[j+1]) {  //找到相同的前后缀
    //             j++;
    //         }
    //         next[i] = j;    //将j赋值给next[i]
          
    //     }
    // }
    // int strStr(string haystack, string needle) {
    //     if(needle.size()==0)
    //     return 0;
    //     int next[needle.size()];
    //     getNext(next,needle); 
    //     int j = -1; //因为next数组记录的起始位置为-1
    //     for ( int i = 0; i < haystack.size() ; i++) {
    //         while (j >=0 && haystack[i] != needle[j+1]) { //不匹配
    //             j = next[j]; //寻找之前匹配的位置
    //         }
    //         if(haystack[i]==needle[j+1]){//匹配成功
    //             j++;
    //         } 
    //         if (j == (needle.size() - 1)) { //文本串s里出现了模式串t
    //             return (i-needle.size() +1);
    //         }
    //     }
    //     return -1;
    // }

    int strStr(string s, string p) {
        int n = s.size(),m = p.size();
        if(m ==0) 
        return 0;
        //设置哨兵
        s.insert(s.begin(),' '); //文本串
        p.insert(p.begin(),' '); //模式串
        vector next(m+1);
        //预处理
        for ( int i =2,j = 0;i<=m;i++) {
            while(j&&p[i]!=p[j+1]) //不匹配
            j=next[j];
            if(p[i]==p[j+1])//匹配
            j++;
            next[i] = j;//将j赋值给next[i]
        }
        //匹配过程
        for(int i=1,sj=0;i<=n;i++) {
            while(j&&s[i]!=p[j+1])
            j=next[j]; //退后
            if(p[j+1]==s[i])
            j++; 
            if(j==m )
            return i-m; 

        }
        return -1;
    }

};


    • 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
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    【模板】KMP字符串匹配

    题目描述

    给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
    现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

    定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
    对于 $s_2$，你还需要求出对于其每个前缀 $s'$ 的最长 border $t'$ 的长度。

    输入格式

    第一行为一个字符串，即为 $s_1$。
    第二行为一个字符串，即为 $s_2$。

    输出格式

    首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。
    最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

    样例 #1

    样例输入 #1

    ABABABC
ABA

    • 1
    • 2

    样例输出 #1

    1
3
0 0 1

    • 1
    • 2
    • 3

    提示

    样例 1 解释

    。

    对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

    数据规模与约定

    本题采用多测试点捆绑测试，共有 3 个子任务。

    • Subtask 1（30 points）：$|s_1| \leq 15$，$|s_2| \leq 5$。
    • Subtask 2（40 points）：$|s_1| \leq 10^4$，$|s_2| \leq 10^2$。
    • Subtask 3（30 points）：无特殊约定。

    对于全部的测试点，保证 $1 \leq |s_1|,|s_2| \leq 10^6$，$s_1, s_2$ 中均只含大写英文字母。

    #include
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j=0;
char a[MAXN],b[MAXN];
int main() {
    //往后移一位输入1开始，这样就不需要从-1开始
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
    {   
        //匹配不成功
        while(j&&b[i]!=b[j+1]) {
            j=kmp[j]; //退后
        }
        //匹配成功
        if(b[i]==b[j+1])
        j++;
        //赋值
        kmp[i]=j;
    }
    j=0;
    for(int i=1;i<=la;i++) {
        while(j>0&&b[j+1]!=a[i])
        j=kmp[j];
        if(b[j+1]==a[i])
        j++;
        if(j==lb)
        {
            cout<

重复的字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。



示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
class Solution {
public:
    // bool repeatedSubstringPattern(string s) {
    //     int n = s.size();
    //     for (int i = 1;i*2<=n;++i) {
    //         if (n%i == 0) {
    //             bool match = true;
    //             for(int j=i;j=0&&s[i]!=s[j+1]) {
                j=next[j];
            }
            if(s[i] == s[j+1]) {
                j++;
            }
            next[i]=j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if(s.size()==0) {
            return false;
        }
        int next[s.size()];
        getNext(next,s);
        int len = s.size();
        //(len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）
        if(next[len-1]!=-1&&len%(len-(next[len-1]+1))==0) {
            return true;
        }
        return false;
    }
};


  • 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

[BOI2009]Radio Transmission 无线传输

题目描述

给你一个字符串 s 1 s_1 s1​，它是由某个字符串 s 2 s_2 s2​ 不断自我连接形成的。但是字符串 s 2 s_2 s2​ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 L L L，表示给出字符串的长度。

第二行给出字符串 s 1 s_1 s1​ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 s 2 s_2 s2​ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

  • 1
  • 2

样例输出 #1

3

  • 1

提示

样例输入输出 1 解释

对于样例，我们可以利用 abc \texttt{abc} abc 不断自我连接得到 abcabcabc \texttt{abcabcabc} abcabcabc，读入的 cabcabca \texttt{cabcabca} cabcabca，是它的子串。

规模与约定

对于全部的测试点，保证 1 < L ≤ 1 0 6 1 < L \le 10^6 1<L≤106。

#include
using namespace std;
#define MAXN 1000010
int kmp[MAXN];
int j;
int L;
char a[MAXN];
int main() {
    cin>>L;
    cin>>a+1;
    for(int i=2;i<=L;i++) {
        while(j>0&&a[i]!=a[j+1])
        j=kmp[j];
        if(a[i]==a[j+1])
        j++;
        kmp[i]=j;
    }
    cout<
  • 相关阅读:
    如何使用websocket+node.js实现pc后台与小程序端实时通信
    外包干了5天，技术退步明显。。。。。
    ZZNUOJ_用Java编写程序实现1527：简单加法(附源码)
    学习Java的第十六天。。。（构造方法、方法重载、this、局部变量和成员变量）
    游戏设计与刚体力学
    算法通关村——字符串反转问题解析
    Tailor：一键式视频智能处理，轻松打造精彩视频！
    STM32单片机OLED经典2048游戏单片机小游戏
    网络编程基础（二）：TCP/IP协议基础：TCP信息头、TCP状态机与握手/挥手、TCP的粘包和粘包、SYN超时与SYN Flood攻击、TIME_WAIT
    蓝桥杯每日一题2023.10.15
  • 原文地址：https://blog.csdn.net/wenjinjie1/article/details/127874728