ACM讲课之字符串

Wesley13
• 阅读 491

本次讲课讲全面介绍字符串以及如何使用字符串解决具体问题。

一、什么是字符串

1.如何存储字符串

平时我们使用的变量有很多,int代表整型变量,double代表浮点型变量,char代表字符型变量,那么对于一个字符串例如“Hello World!”应该如何存储并操作呢。

在C语言里,我们可以char数组进行存储,例如:

1 char str1[] = "Hello World!";
2 char* str2 = "Hello World!";
3 char str3[20] = "Hello World!";

对str1、2、3进行输出都为“Hello World!”,这三种方式构造一个字符串的区别有哪些?我们输出他们的空间长度(注意是占用的空间长度而不是字符串长度)。

1     int len1 = sizeof(str1)/sizeof(char);
2     int len2 = sizeof(str2)/sizeof(char);
3     int len3 = sizeof(str3)/sizeof(char);
4     printf("%d\n%d\n%d\n",len1,len2,len3);结果为:13    4    20

(此处应对上诉结果进行解释说明 ==)

既然字符串可以存储在一个字符数组里面,那么如何对字符串进行操作想必也就非常清楚了。需要注意的是,对于计算机可以字符和一个整型变量没有任何区别,它们都是数据,所以对整型变量可以做的操作都可以对一个字符进行同样的操作。

2.ASCII编码

众所周知字符在C/C++里面是以ASCII码的形式存储在计算机中,既然字符串是存储在字符数组里面的,其实也就是多个字符的一个有序集合。它也遵守和字符同样的的规则,例如'A'的ASCII码为65,如果我们进行下列语句

1 char ch = 'A';
2 if(ch == 'A'){
3     ch = ch + 5;        
4 }
5 else {
6     ch = ch - 1;  
7 }

那么这里ch的值应该变成多少了呢?此时的ch又代表哪个字符呢?

3.std::string

是不是没见过这是什么东西,它其实就是character string(字符串),这是一个C++的语句,意思就是调用std(标准命名空间)里面的string类,可能你也已经猜到了string是用来干什么的,是的它可以直接定义一个字符串变量,并且能够直接对串进行操作。

什么意思呢?我们既然已经能够用字符数组存储字符串了,为什么还需要多个string呢,因为我们前面说了字符串数组相当于一个字符的有序集合,归根到底还都是单个字符,而字符串变量string才是真正的字符串,它可以直接对串操作,例如下列语句:

std::string str = "Hello";
str += " World";
str += "!";

如果仅仅只是这样,那么string并不显得强大,事实上string支持下面的功能

我是传送门:string的用法

但是值得注意的是,string是c++语言的东西,在c语言中并不能使用,而且string只能通过cin流进行读入操作,同样可以使用下标对string字符串进行每一位的访问以及操作。

C++也还有很多C语言没有的容器,通过这些容器对做题有很大帮助,而且这些容器对于一个ACMer来说是必须要掌握的,详情请戳:

STL容器(Stack, Queue, List, Vector, Deque, Priority_Queue, Map, Pair, Set, Multiset, Multimap)

二、字符串操作

1.空格、换行符

我们知道使用scanf("%s",s);读入一个字符串遇到空格和换行符自动跳出,但是对于一个字符串不可能都没有空格以及换行呀,如果是需要读入一个句子那该怎么办呢,对于C语言,我提供了下列几种方法供参考

 1 //方法一——判断是否为空格选择继续读入还是跳出
 2     char s[100],ch;
 3     scanf("%s",s);
 4     ch = getchar();
 5     while(ch == ' '){
 6         int len = strlen(s);
 7         s[len] = ' ';
 8         scanf("%s",s+len+1);
 9         ch = getchar();
10     }
11 
12 //方法二——利用格式符%[]设置结束符
13     char s[100];
14     scanf("%[^\n]",s);
15 
16 
17 //方法三——利用不安全的gets进行读入
18     char s[100];
19     gets(s);

三种方法都可以进行读入以换行符为结束符带有空格的字符串,但是我推荐最好使用第一种,为什么?

(此处应对上述进行解释说明)

在C++语言中,想要读入这样的串,我也同样提供几种方法供参考

1 //方法一——使用cin流对字符串进行读入
2     char s[100];
3     cin.getline(s,100);
4 
5 //方法二——使用getline进行string类读入
6     string s;
7     getline(cin,s);

下面以一个例题为例,对字符串的具体操作进行讲解

题目链接:http://120.78.128.11/Problem.jsp?pid=1716

下面我贴出C语言和C++语言的代码

 C语言:

 1 #include <stdio.h>
 2 #include <string.h>
 3 char s1[10005],s2[105];
 4 
 5 void read(char *s){
 6     int ch;
 7     scanf("%s",s);
 8     ch = getchar();
 9     while(ch == ' '){
10         int len = strlen(s);
11         s[len] = ' ';
12         scanf("%s",s+len+1);
13         ch = getchar();
14     }
15 }
16 
17 int main(){
18     int t;
19     scanf("%d",&t);
20     while(t--){
21         read(s1),read(s2);//读入字符串
22         int len1 = strlen(s1),len2 = strlen(s2);
23         int flag = -1,i,j;
24         for(i = 0; i < len1; i++){
25             if(s1[i] == s2[0]){
26                 for(j = 0; j < len2; j++){
27                     if(j == len2-1 && s1[i+j] == s2[j])
28                         flag = i+1;
29                     if(s1[i+j] != s2[j])
30                         break;
31                 }
32             }
33         }
34         printf("%d\n",flag);
35     }
36     return 0;
37 }

C++语言:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 string s1,s2;
 5 
 6 int main(){
 7     int t;
 8     cin>>t;
 9     cin.get();
10     while(t--){
11         getline(cin,s1),getline(cin,s2);
12         int pos = s1.find(s2);
13         cout << (pos==-1?-1:pos+1) << endl;
14     }
15     return 0;
16 }

这也是为什么要用C++的原因,C++内置函数以及操作实在是太强大了,两个C中较为冗长的函数在C++中都只要用一句便实现了。

另一个例题:http://120.78.128.11/Problem.jsp?pid=1924

C语言代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 char s[1000005];
 4 
 5 void read(char *s){
 6     int ch;
 7     scanf("%s",s);
 8     ch = getchar();
 9     while(ch == ' '){
10         int len = strlen(s);
11         s[len] = ' ';
12         scanf("%s",s+len+1);
13         ch = getchar();
14     }
15 }
16 
17 int main(){
18     int t,i;
19     scanf("%d",&t);
20     while(t--){
21         read(s);
22         int len = strlen(s);
23         for(i = 0; i < len; i++){
24             if(i == 0){
25                 putchar(s[i]-32);
26             }
27             if(s[i] == ' '){
28                 putchar(s[i+1]-32);
29             }
30         }
31         puts("");
32     }
33     return 0;
34 }

C++代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 string s;
 5 
 6 int main(){
 7     int t;
 8     cin>>t;
 9     cin.get();
10     while(t--){
11         getline(cin,s);
12         int len = s.size();
13         cout << char(s[0]-32);
14         for(int i = 1; i < len; i++){
15             if(s[i] == ' ')
16                 cout << char(s[i+1]-32);
17         }
18         cout << endl;
19     }
20     return 0;
21 }

2.字符串比较

我们知道可以通过一位一位的模拟进行字符串比较,但要是两个字符串都很长怎么办,我们容易得出暴力方法进行匹配的时间复杂度为O(n*m),n和m就是两个字符串的长度,通过一些算法我们可以进行匹配优化,例如我们可以利用KMP算法在O(n+m)的时间复杂度内进行匹配。

下面是KMP的算法讲解

我是传送门:KMP算法

传送门:KMP例题

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Karen110 Karen110
2年前
一篇文章带你了解JavaScript日期
日期对象允许您使用日期(年、月、日、小时、分钟、秒和毫秒)。一、JavaScript的日期格式一个JavaScript日期可以写为一个字符串:ThuFeb02201909:59:51GMT0800(中国标准时间)或者是一个数字:1486000791164写数字的日期,指定的毫秒数自1970年1月1日00:00:00到现在。1\.显示日期使用
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Easter79 Easter79
2年前
SpringBoot自定义序列化的使用方式
场景及需求:项目接入了SpringBoot开发,现在需求是服务端接口返回的字段如果为空,那么自动转为空字符串。例如:\    {        "id":1,        "name":null    },    {        "id":2,        "name":"x
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
JavaScript常用函数
1\.字符串长度截取functioncutstr(str,len){vartemp,icount0,patrn/^\x00\xff/,strre"";for(vari
Stella981 Stella981
2年前
SpringBoot自定义序列化的使用方式
场景及需求:项目接入了SpringBoot开发,现在需求是服务端接口返回的字段如果为空,那么自动转为空字符串。例如:\    {        "id":1,        "name":null    },    {        "id":2,        "name":"x
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
3个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这