算法小课堂(七)字符串

news/2025/2/23 4:17:47/

一、概念

1.1相关概念

0C++中有两种字符串表示形式:C风格字符串和string类类型。

C风格字符串是

  • 字符数组使用null字符\0终止的一维字符数组,
  • 字符指针是一个指针变量,里面存放一个字符的地址

而string类处理起字符串来会方便很多,完全可以代替C语言中的字符数组或字符串指针。

使用string类需要文件包含: #include <string>

1.2字符串的构造方法

  • string s; //空串
  • string s=“nefuer”;//利用常量字符串构造字符串
  • string t = s;//利用已有的字符串对象赋值
  • string (3, ‘a’);//”aaa” string (“china”,1,3);//”hin”
  • string str3 = s+ t;

1.3字符串的基本操作

1.3.1输入

C++中的输入大致有6种方法:cin,cin.get(),cin.getline(),gets(),getchar()

cin
用法一:最常用的方法,接收一个字符串,无论是string还是char a[10],都是一样,但是遇到“空格”,“TAB”,"回车"都结束。

#include<iostream>
#include<string>
using namespace std;
int main()
{string a, b;cin >> a >> b;cout << a << endl;cout << b << endl;return 0;
}

cin.get()

用法一:cin.get(字符变量名)可以用来接收字符

#include<iostream>
#include<string>
using namespace std;
int main()
{char ch;ch = cin.get();//或者是cin.get(ch);cout << ch;return 0;
}

用法二:cin.get(字符数组名,接收字符个数),用来接收一行字符串(可以接收空格),这个最大的用途是可以定量的接收字符的个数(但是要注意,如果定义的数组的个数是20,则实际上最大接收19个字符(可以小于19),还要加上'\0')

这个方法只能正针对于是字符数组,不能使用string来输入。

#include<iostream>
#include<string>
using namespace std;
int main()
{char a[20];//string a;报错cin.get(a, 20);cout << a;return 0;
}

cin.getline()
可以接收空格,并且输出。浅显的用法其实和cin.get()差不多。(也不能使用string来进行输入)

#include<iostream>
#include<string>
using namespace std;
int main()
{char a[20];cin.getline(a, 20);cout << a;return 0;
}

更加深层的用法其实就是cin.getline()的原型,这个函数本来有三个参数,分别是字符串的位置,接受个数,结束字符。
如果将例子中cin.getline()改为cin.getline(m,5,'a');当输入jlkjkljkl时输出jklj,输入jkaljkljkl时,输出jk
当用在多维数组中的时候,也可以用cin.getline(m[i],20)之类的用法:
 

#include<iostream>
#include<string>
using namespace std;int main ()
{char m[3][20];for(int i=0;i<3;i++){cout<<"\n请输入第"<<i+1<<"个字符串:"<<endl;cin.getline(m[i],20);}cout<<endl;for(int j=0;j<3;j++)cout<<"输出m["<<j<<"]的值:"<<m[j]<<endl;return 0;
}

getline()
接收一个字符串,可以接收空格并输出,不过要包含#include<string>
这也就弥补了之前cin.getline()和cin.get()的不能读取string的一个小的弊端
这里还要将这个写法稍微改正一下getline(cin,字符串数组名);

用法一:一行,默认换行符结束

#include<iostream>
#include<string>
using namespace std;
int main()
{string s;getline(cin,s);cout << s;return 0;
}

用法二://一行或者多行,以第三个参数结束

#include<iostream>
#include<string>
using namespace std;
int main()
{string s;getline(cin,s,'.');cout << s;return 0;
}

gets()
接收一个字符串,可以接收空格并且输出,需要包含#include<string>
但是这个函数有些奇葩的是,这个函数必须要包含头文件string,但是这个函数却不能直接对变量string来进行赋值。

#include<iostream>
#include<string>
using namespace std;
int main()
{char s[10];gets_s(s);cout << s;return 0;
}

这个函数不安全

 getchar()
获取单个字符,需要包含#include<string>。
这个函数尽量少用

#include<iostream>
#include<string>
using namespace std;
int main()
{char ch;ch = getchar();cout << ch;return 0;
}

适合用来吃回车

1.3.2输出

setw()函数

C++中的setw()函数是在输出操作中使用的字段宽度设置,此函数的作用是:设置输出的域宽,n表示字段宽度。

当后面紧跟着的输出字段长度小于n的时候,在该字段前面用空格补齐;当输出字段长度大于n时,全部整体输出。

包含在头文件为#include <iomanip>中,其中io代表输入输出,manip是manipulator(操纵器)的缩写iomanip的作用

#include <iostream>
using namespace std;#include <iomanip>int main()
{cout << 123456789 << endl;cout << setw(2) << 123 << setw(7) << 456789 << endl;return 0;
}

 其他常见的iomanip标准库函数

 setfill(n)

 设置字符填充,c可以是字符常或字符变量

 setprecision(n) 设置浮点数的有效数字为n位
 setw(n) 设置字段宽度为n位
​#include <iostream>
#include <iomanip> // 包含设置格式的库using namespace std;int main() {char c = '#';double num = 3.14159265359;cout << setfill(c) << setw(10) << "hello" << endl; // 输出 "####hello"cout << fixed << setprecision(3) << num << endl; // 输出 "3.142"cout << setfill('0') << setw(6) << 42 << endl; // 输出 "000042"return 0;
}​

二、字符串的操作

2.1字符串的基本操作

字符串的基本操作   string s,t;

  • 赋值:s=“pear”; t=s;
  • 关系判断: s<t  
  •                  s==t
  • 连接: s+t 添加:
  •                  s+=t;              
  •                  s.append(t);          
  •                  s.push_back(‘a’);
  • 交换:swap()              
  •            s.swap( t )
  • 长度:s.length()  s.size( )

2.2字符串的常见操作

2.2.1字符串的访问

  1. 使用下标运算符[]。例如:
    string str = "Hello";
    cout << str[0] << endl; // 输出 H
  2. 使用at()函数。例如:
    string str = "Hello";
    cout << str.at(0) << endl; // 输出 H
  3. substr()函数获取子串

         string substr(int pos=0, int len=string::npos) const; 获取从下标pos开始的len个字符形  成子串,如果省略len或者pos+len超出字符串长度则默认到最后一个字符。

string str = "Hello World";
string substr = str.substr(0, 5); // 获取 "Hello"

2.2.2字符串的查找

1.find()函数用于在string字符串中查找子字符串第一次出现的位置。

size_t find (const string& str, size_t pos = 0) const;

第一个参数为待查找的子字符串,它可以是string字符串,也可以是C风格的字符串。第二个参数为查找的起始位置,默认值为0。

string str = "Hello World";
int index = str.find("World"); // 获取 6

2.rfind()函数用于在字符串中从后向前查找子串(字符)首次出现位置(rfind从后向前逆向查,但匹配是正向匹配的)

size_t rfind (const string& str, size_t pos = npos) const;

第一个参数为待查找的子字符串,它可以是string字符串,也可以是C风格的字符串。第二个参数为查找的起始位置,默认值为npos。

string str = "Hello World";
int index = str.rfind("o"); // 获取 7

3.s.find_first_of(str)和s.find_last_of(str)

找到目标字符在字符串中第一次出现和最后一次出现的位置

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main(){string s,c;s="baaaaab";c="b";cout<<"first index:"<<s.find_first_of(c)<<endl;cout<<"last index:"<<s.find_last_of(c)<<endl;
}

4查找目标字符串在字符串出现的总次数

#include<bits/stdc++.h>
#include<iostream>using namespace std;int main(){// 定义两个字符串变量s和c,分别存储原始字符串和子串string s,c;// 定义两个整数变量index和sum,分别存储当前匹配的位置和总匹配次数int index,sum;// 初始化index和sum为0index=0;sum=0;// 使用while循环读入s和c,直到输入结束while(cin>>s>>c){// 使用while循环在s中查找c,使用find函数返回匹配的位置,如果没有匹配,返回string::nposwhile((index=s.find(c,index))!=string::npos){// 输出当前匹配的次数和位置cout<<"sum: "<<sum+1<<" index: "<<index<<endl;// 更新index为当前匹配位置加上c的长度,以避免重复匹配index+=c.length();// 更新sum为当前匹配次数加一sum++;
}// 输出最终的匹配次数cout<<sum<<endl;
}// 返回0表示程序正常结束return 0;
}
/*
banana na
*/

string::npos是一个常量静态成员值,它是size_t类型的元素能表示的最大值12。它实际上表示字符串的结尾

2.2.3字符串插入

字符串insert( )函数

在原串下标为pos的字符前插入字符串str

basic_string& insert (size_type pos, const basic_string& str);

str从下标为pos1开始数的n个字符插在原串下标为pos的字符前

basic_string& insert (size_type pos, const basic_string& str, size_type pos1, size_type n);

在原串下标为pos的字符前插入n个字符c
 

basic_string& insert (size_type pos, size_type n, char c);

举例

#include<iostream>
using namespace std;
int main()
{string str="hello";string s="Hahah";str.insert(1,s);//在原串下标为1的字符e前插入字符串scout<<str<<endl;string str1="hello";char c='w';str1.insert(4,5,c);//在原串下标为4的字符o前插入5个字符ccout<<str1<<endl;string str2="hello";string s2="weakhaha";str2.insert(0,s2,1,3);//将字符串s2从下标为1的e开始数3个字符,分别是eak,插入原串的下标为0的字符h前cout<<str2<<endl;return 0;
}

2.2.4替换字符串的子串:replace( ) 函数

将下标pos开始的len个字符替换为特定字符串str

        string& replace (size_t pos, size_t len, const string& str);

将迭代器beg和end中间的字符替换为str
       string& replace (iterator beg, iterator end, const string& str);

#include <iostream>
#include <string>
using namespace std;int main() {// 创建一个字符串对象string s = "Hello world!";// 调用第一个函数,将下标为6开始的5个字符替换为"China"s.replace(6, 5, "China");// 输出替换后的字符串cout << s << endl; // Hello China!// 调用第二个函数,将迭代器s.begin()和s.begin()+5之间的字符替换为"Hi"s.replace(s.begin(), s.begin() + 5, "Hi");// 输出替换后的字符串cout << s << endl; // Hi China!return 0;
}

2.2.5删除字符串中的子串:erase( )函数

删除字符串中的子串:erase( )函数

删除迭代器pos指向的元素         string& erase(iterator pos);

删除迭代器pos开始的len个字符         string& erase (iterator pos=0,size_t len=npos);

删除迭代器first到last中间字符            string.erase(iterator first,iterator last);  

#include <iostream>
#include <string>
using namespace std;int main() {// 创建一个字符串对象string s = "Hello world!";// 调用第一个函数,删除下标为6开始的5个字符s.erase(6, 5);// 输出删除后的字符串cout << s << endl; // Hello !// 调用第二个函数,删除迭代器s.begin()+5指向的字符s.erase(s.begin() + 5);// 输出删除后的字符串cout << s << endl; // Hello!// 调用第三个函数,删除迭代器s.begin()+2和s.end()-1之间的字符s.erase(s.begin() + 2, s.end() - 1);// 输出删除后的字符串cout << s << endl; // He!return 0;
}

2.2.6string与C风格字符串的转换

c_str( )函数 

c_str ()函数是string类的一个成员函数,它返回一个指向正规C字符串的指针常量,内容与本string串相同

#include <iostream>
#include <string>
using namespace std;int main() {// 创建一个字符串对象string s = "Hello world!";// 调用c_str ()函数,返回一个指向C字符串的指针const char* c = s.c_str();// 输出C字符串cout << c << endl; // Hello world!return 0;
}

2.3string对象的STL常用算法

string 对象也可以看作一个顺序容器,它支持随机访问迭代器,也有 begin 和 end 等成员函数。STL 中的许多算法也适用于 string 对象。 计数,查找,删除,排序等操作都可以利用STL算法来完成。

2.3.1计数

count( ): 查找值value在容器中的个数,它可以用于任何支持迭代器的容器,如vector,list,set,map等。它的用法是:

count(first, last, value);

其中first和last是容器的首尾迭代器,value是要查找的元素。它的返回值是一个整数,表示value在容器中出现的次数

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int main() {string s = "hello world"; // 定义一个string对象int n = count(s.begin(), s.end(), 'l'); // 查找'l'在s中的个数cout << n << endl; // 输出3return 0;
}

2.3.2排序与反序操作

sort( ):排序

      sort(s.begin( ) , s.end( ) );  

    //对字符串中字符进行升序排序 reverse( ):

反序,将序列 [beg , end)的元素在原容器中反序  

         reverse(iterator beg,iterator end);      

         reverse(s.begin( ) , s.end( ) );   //对字符串进行反序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;bool comp(char a, char b) { // 定义一个比较函数,按照字母表顺序的逆序比较字符return a > b;
}int main() {string s = "hello world"; // 定义一个string对象sort(s.begin(), s.end()); // 对s中的字符进行升序排序cout << s << endl; // 输出 dehllloorwsort(s.begin(), s.end(), comp); // 对s中的字符按照comp函数指定的规则进行排序cout << s << endl; // 输出 wroollldhhereverse(s.begin(), s.end()); // 将s中的字符反转cout << s << endl; // 输出 ehhdllloorwreturn 0;
}

2.3.3删除元素remove( )|remove_if( )

remove(first, last, value); // 删除[first, last)区间内等于value的元素,并返回新的超尾值的迭代器

 remove(iterator beg, iterator end, value);

 注意:remove函数并不是真的删除元素,它只是通过迭代器的指针向前移动来删除,将没有被删除的元素放在容器前面,并返回一个指向新的超尾值的迭代器,如果需要删除元素,需要结合对应容器的earse函数。

remove_if( )函数:删除容器中满足fun函数中条件的元素,效果等同remove函数,可以用来删除多个元素。

remove_if(iterator beg, iterator end, fun);

2.3.4替换元素 replace():

replace() 是字符串的一个方法,它可以用来替换字符串中的某些字符或子串。

replace(iterator beg, iterator end, oldvalue, newvalue);

举例

#include <iostream>
#include <string>
using namespace std;int main() {string s = "Hello World"; // 定义一个string对象s.replace(0, 5, "Hi"); // 用"Hi"替换从0开始长度为5的子串cout << s << endl; // 输出 Hi Worlds.replace(s.begin(), s.begin() + 3, "Bye"); // 用"Bye"替换从迭代器s.begin()到s.begin() + 3的子串cout << s << endl; // 输出 Bye Worlds.replace(4, 5, "Bye", 0 ,3); // 用"Bye"的从0开始长度为3的子串替换从4开始长度为5的子串cout << s << endl; // 输出 Bye Byes.replace(0 ,3 , "Hello"); // 用C字符串"Hello"替换从0开始长度为3的子串cout << s << endl; // 输出 Hello Byes.replace(s.begin(), s.begin() + 5 , "Hi"); // 用C字符串"Hi"替换从迭代器s.begin()到s.begin() + 5的子串cout << s << endl; // 输出 Hi Byes.replace(0 ,2 , "Hello", 3); // 用C字符串"Hello"的前3个字符替换从0开始长度为2的子串cout << s << endl; // 输出 Hel Byes.replace(s.begin(), s.begin() +3 , "Hi",2); // 用C字符串"Hi"的前2个字符替换从迭代器s.begin()到s.begin() +3 的子串cout << s << endl; // 输出 Hi Byes.replace(0 ,2 ,3 ,'*'); // 用3个字符'*'替换从0开始长度为2的子串cout << s << endl; // 输出 *** Byes.replace(s.begin(), s.end(), "Hello World"); // 用"Hello World"替换从迭代器s.begin()到s.end()的子串,即整个字符串cout << s << endl; // 输出 Hello Worldreturn 0;
}

三、例题

3.1反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

#include <iostream>
#include <vector>using namespace std;void reverseString(vector<char>& s) {int left = 0, right = s.size() - 1;while (left < right) {swap(s[left], s[right]);left++;right--;}
}int main() {vector<char> s = {'h', 'e', 'l', 'l', 'o'};reverseString(s);for (char c : s) {cout << c << " ";}cout << endl;return 0;
}

另一种形式

#include <iostream>
#include <vector>using namespace std;void reverseString(vector<char>& s) {for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {swap(s[i],s[j]);}
}int main() {vector<char> s = {'h', 'e', 'l', 'l', 'o'};reverseString(s);for (char c : s) {cout << c << " ";}cout << endl;return 0;
}

另一种形式

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {vector<char> s = {'h', 'e', 'l', 'l', 'o'};reverse(s.begin(),s.end());for (char c : s) {cout << c << " ";}cout << endl;return 0;
}

3.2反转字符串II

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

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

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"
示例 2:

输入:s = "abcd", k = 2
输出:"bacd"
 

提示:

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

#include <iostream>
#include <string>
#include <algorithm>using namespace std;string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += (2 * k)) {// 1. 每隔 2k 个字符的前 k 个字符进行反转// 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符if (i + k <= s.size()) {reverse(s.begin() + i, s.begin() + i + k );} else {// 3. 剩余字符少于 k 个,则将剩余字符全部反转。reverse(s.begin() + i, s.end());}}return s;
}int main() {string s = "abcdefg";int k = 2;string res = reverseStr(s, k);cout << res << endl;  // 输出:bacdfegs = "abcd";k = 2;res = reverseStr(s, k);cout << res << endl;  // 输出:bacdreturn 0;
}

3.3翻转字符串里的单词

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

示例 1:

输入:s = "the sky is blue"
输出:"blue is sky the"
示例 2:

输入:s = "  hello world  "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格。
示例 3:

输入:s = "a good   example"
输出:"example good a"
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
 

提示:

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>using namespace std;string join(vector<string>& words, string delimiter) {string result = "";int n = words.size();for (int i = 0; i < n; i++) {result += words[i];if (i < n - 1) {result += delimiter;}}return result;
}string reverseWords(string s) {vector<string> words; // 存储单词的vectorstring word = ""; // 存储当前单词的字符串for (char c : s) {if (c == ' ') { // 遇到空格,当前单词结束,将其加入vector中if (!word.empty()) {words.push_back(word);word = "";}} else { // 不是空格,将字符加入当前单词的字符串中word += c;}}if (!word.empty()) {words.push_back(word); // 将最后一个单词加入vector中}reverse(words.begin(), words.end()); // 翻转vectorstring word0 = join(words, " ");return word0; // 使用string的join方法连接单词
}int main() {string s1 = "the sky is blue";cout << reverseWords(s1) << endl; // "blue is sky the"string s2 = "  hello world  ";cout << reverseWords(s2) << endl; // "world hello"string s3 = "a good   example";cout << reverseWords(s3) << endl; // "example good a"return 0;
}

快慢指针

#include <iostream>
#include <string>
#include<algorithm>
using namespace std;// 定义一个函数,用于去除字符串中多余的空格
void removeExtraSpaces(string& s) {int slow = 0; // 定义一个慢指针,用于记录去除空格后的字符串长度for (int i = 0; i < s.size(); ++i) { // 遍历字符串中的每个字符if (s[i] != ' ') { // 如果当前字符不是空格if (slow != 0) s[slow++] = ' '; // 如果慢指针不为零,说明前面已经有单词了,需要在单词间加一个空格while (i < s.size() && s[i] != ' ') { // 把当前单词的所有字符复制到慢指针指向的位置s[slow++] = s[i++];}}}s.resize(slow); // 调整字符串的大小为慢指针的值,去除末尾多余的空格
}
// 定义一个函数,用于反转字符串中的单词顺序
void reverseWords(string& s) {removeExtraSpaces(s); // 先调用上面定义的函数,去除字符串中多余的空格reverse(s.begin(), s.end()); // 反转整个字符串,使用<algorithm>库中的reverse函数int start = 0; // 定义一个变量,用于记录每个单词的起始位置for (int i = 0; i < s.size(); ++i) { // 遍历字符串中的每个字符if (s[i] == ' ') { // 如果当前字符是空格,说明找到了一个单词的结束位置reverse(s.begin() + start, s.begin() + i); // 反转这个单词,使用<algorithm>库中的reverse函数start = i + 1; // 更新下一个单词的起始位置为当前位置加一}}reverse(s.begin() + start, s.end()); // 反转最后一个单词,使用<algorithm>库中的reverse函数
}int main() {string s1 = "the                   sky is blue";//removeExtraSpaces(s1);reverseWords(s1);cout << s1 << endl;  // 输出 "blue is sky the"string s2 = "  hello world  ";reverseWords(s2);cout << s2 << endl;  // 输出 "world hello"string s3 = "a good   example";reverseWords(s3);cout << s3 << endl;  // 输出 "example good a"return 0;
}

3.4KMP算法

实验书模板

#include <iostream>
#include<cstring>
using namespace std;
bool getNext(char T[], int length, int *next) {int i = 1;int j = 0;next[i-1] = 0;while(i < length) {if(j == 0 || T[i-1] == T[j-1]) {i ++;j ++;next[i-1] = j;}else {j = next[j-1];}}return true;
}void getnextval(char T[], int lengtht, int *nextval) {int i = 1;int j = 0;nextval[i-1] = 0;while(i < lengtht) {if(T[i-1] == T[j-1] || j == 0) {i ++;j ++;if(T[i-1] != T[j-1]) nextval[i-1] = j;else nextval[i-1] = nextval[j-1];}else j = nextval[j-1];}
}int KMP(char S[], int lengths, char T[], int lengtht) {int *next;next = new int[lengtht];getNext(T, lengtht, next);for(int i = 0; i < lengtht; i ++) {cout << *(next + i) << " ";}cout << endl;int *nextval;nextval = new int[lengtht];getnextval(T, lengtht, nextval);for(int i = 0; i < lengtht; i ++) {cout << *(nextval + i) << " ";}cout << endl;int i = 1;int j = 1;while(i <= lengths && j <= lengtht) {if(j == 0 || S[i-1] == T[j-1]) {i ++;j ++;}else {j = next[j-1];}}if(j > lengtht) return i - lengtht;else return -1;
}int main() {char S[] = "abagooglegg";char T[] = "abcaabbcabcaabdab";//char S[100],T[100];//cin>>S;//cin>>T;int lengths = strlen(S);int lengtht = strlen(T);int res = KMP(S,lengths, T,lengtht);cout << res;cout << endl;return 0;
}

具体题目

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

示例 1:

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

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
 

提示:

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

暴力匹配

// 暴力匹配
int i = 0, j = 0;
while (i < s.length())
{if (s[i] == p[j])++i, ++j;elsei = i - j + 1, j = 0;if (j == p.length())  // 匹配成功{// 对s[i - j .. i - 1]进行一些操作cout << i - j << endl;i = i - j + 1;j = 0;}
}

KMP

#include <iostream>
#include <vector>
#include <string>using namespace std;void getNext(int* next, const string& s) {int j = 0;      //表示前缀的末尾next[0] = 0;    //next[0]初始化为0for(int i = 1; i < s.size(); i++) {    //i表示后缀的末尾while (j > 0 && s[i] != s[j]) {   //当j>0且两个字符不相等时,往前跳j = next[j - 1];    //因为j是前缀末尾,所以需要找到前缀的前缀的末尾}if (s[i] == s[j]) { //如果相等,最长匹配数加1j++;}next[i] = j;    //将最长匹配数保存在next数组中}
}int strStr(string haystack, string needle) {if (needle.size() == 0) {   //如果needle为空,返回0return 0;}int next[needle.size()];    //定义next数组,大小为needle的长度getNext(next, needle);  //求next数组int j = 0;  //j表示模式串needle的下标for (int i = 0; i < haystack.size(); i++) { //i表示主串haystack的下标while(j > 0 && haystack[i] != needle[j]) {    //当两个字符不相等时,往前跳j = next[j - 1];    //因为j是前缀末尾,所以需要找到前缀的前缀的末尾}if (haystack[i] == needle[j]) { //如果相等,最长匹配数加1j++;}if (j == needle.size() ) {  //如果j等于模式串needle的长度,说明完全匹配return (i - needle.size() + 1); //返回下标,因为i是主串下标,所以需要减去needle的长度,加1是因为数组下标从0开始}}return -1;  //未匹配成功,返回-1
}int main() {string haystack = "hello world";string needle = "lo";int index = strStr(haystack, needle);cout << index << endl;  //预期输出为3haystack = "aaaaa";needle = "bba";index = strStr(haystack, needle);cout << index << endl;  //预期输出为-1return 0;
}

3.5重复的子字符串

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:
输入: "aba"
输出: False

示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

暴力解法

#include <iostream>
#include <string>using namespace std;bool repeatedSubstringPattern(string s) {int n = s.size();// 枚举所有可能的子串长度for (int len = 1; len <= n/2; len++) {if (n % len == 0) { // 如果字符串长度是子串长度的整数倍bool flag = true;string substr = s.substr(0, len); // 取出第一个子串// 逐个检查所有子串是否相同for (int i = len; i < n; i += len) {string temp = s.substr(i, len);if (temp != substr) {flag = false;break;}}if (flag) {return true;}}}return false;
}int main() {string s1 = "abab";string s2 = "aba";string s3 = "abcabcabcabc";cout << repeatedSubstringPattern(s1) << endl; // 输出 "1",即 truecout << repeatedSubstringPattern(s2) << endl; // 输出 "0",即 falsecout << repeatedSubstringPattern(s3) << endl; // 输出 "1",即 truereturn 0;
}

移动匹配

#include <iostream>
#include <string>using namespace std;bool repeatedSubstringPattern(string s) {string t = s + s;t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾if (t.find(s) != std::string::npos) return true; // 如果 t 中包含 s,返回 truereturn false;
}int main() {string s = "abcabcabcabc";if (repeatedSubstringPattern(s)) {cout << "The string \"" << s << "\" can be formed by repeating a substring." << endl;} else {cout << "The string \"" << s << "\" cannot be formed by repeating a substring." << endl;}return 0;
}


http://www.ppmy.cn/news/66937.html

相关文章

unity UGUI系统梳理 -交互组件

概述 unity 中的交互组件可用于处理交互&#xff0c;例如鼠标或触摸事件以及使用键盘或控制器进行的交互 1、按钮 (Button) Button详解 2、开关 (Toggle) Background&#xff1a;背景图片&#xff0c;控制toggle组件的背景颜色改变&#xff0c;从而展示此物体是否被选中的…

月薪低于5千元必看,省钱购物攻略,本人亲测有效

作为资深的网购用户&#xff0c;我不允许我的姐妹们还不知道&#xff0c;网上购物如何省钱&#xff1f;如果你是学生党&#xff0c;或者月薪低于5千元&#xff0c;一定要看一看&#xff01;学会了不但能提升生活品质&#xff0c;还能帮你省下好多钱~ 同样的东西&#xff0c;我…

JavaScript全解析——正则表达式

正则——RegExp ●正则也叫正则表达式&#xff0c;又名 “规则表达式” ●正则是JS中的数据类型, 是一个复杂数据类型 ●由我们自己来书写 “规则”&#xff0c;专门用来检测 字符串 是否符合 “规则” 使用的 ●我们使用一些特殊的字符或者符号定义一个 “规则公式”&#xf…

STL-stack容器和queue容器

stack概念&#xff1a;stack是一种先进后出(First In Last Out,FILO)的数据结构&#xff0c;它只有一个出口 栈中只有顶端的元素才可以被外界使用&#xff0c;因此栈不允许有遍历行为 与queue相似&#xff0c;stack也是一个适配器类&#xff0c;它给底层vector提供了典型的栈接…

cleanmymac在哪下载?中文官网安装教程

CleanMyMac是一个系统清理工具&#xff0c;删除系统缓存文件 , 多余的应用程序语言包 , PowerPc软件运行库等。 是个给你的硬盘瘦身的好工具。 系统&#xff1a;macOS 10.14&#xff08;在10.15以及Big Sur中的安装激活教程相同&#xff09;登录CleanMyMac X下载页面&#xff0…

字节给的比我想的还多?网友看完:打死也要去

曾经的互联网是PC的时代&#xff0c;随着智能手机的普及&#xff0c;移动互联网开始飞速崛起。而字节跳动抓住了这波机遇&#xff0c;2015年&#xff0c;字节跳动全面加码短视频&#xff0c;从那以后&#xff0c;抖音成为了字节跳动用户、收入和估值的最大增长引擎。 自从字节…

1-Zookeeper简介

1-Zookeeper简介 ①官网 官网 https://zookeeper.apache.org/中文网站 https://zookeeper.net.cn/ ②简介 ZooKeeper 是分布式应用程序的分布式开源协调服务。它公开了一组简单的原语&#xff0c;分布式应用程序可以基于这些原语实现更高级别的同步、配置维护、组和命名服务…

Unity 中常见的开发设计模式

以下是 Unity 中常见的开发设计模式的详细介绍&#xff1a; 单例模式 介绍 单例模式是一种常见的设计模式&#xff0c;它确保一个类只有一个实例&#xff0c;并提供全局访问点来访问该实例。 方法 单例模式的实现方法是将类的构造函数私有化&#xff0c;这样就不能通过 ne…