字符串
1. 字符串的定义
字符串是由零个或多个字符组成的有限序列。其中最外边的双引号（或单引号）不是串的内容，它们是串的标志。
2. 字符串的存储结构及其基本运算
分为顺序和链式储存结构，这里笔者只列出顺序串
2.1 顺序串
2.1.1 串的复制
void StrCopy(String s,String t)
{
for(int i = 0;i < t.length; i++)
{
s.data[i] = t.data[i];
}
s.length = t.length;
}2.1.2 判断串相等
bool StrEqual(String s,String t)
{
bool result = true;
if (s.length != t.length)
{
result = false;
}
else
{
for(int = 0;i < s.length; i++)
{
if(s.data[i] != t.data[i])
{
result = false;
break;
}
}
}
return result;
}2.1.3 求串长
int StrLength(String s)
{
return s.length;
}2.1.4 串的连接
String Concat(String s,String t)
{
String str;
str.length = s.length + t.length;
for(int i = 0; i < s.length; i++)
{
str.data[i] = s.data[i];
}
for(int i = 0; i < t.length ;i++)
{
str.data[s.length + i] = t.data[i];
}
return str;
}2.1.5 求子串
String SubStr(String s,int i,int j)
{
String str;
str.length = 0;
if(i <= 0 || i > s.length || j < 0 || i+j-1 > s.length)
{
return str;
}
for(int k = i-1;k < i+j-1;k++)
{
str.data[k-i+1] = s.data[k];
}
str.length = j;
return str;
}2.1.6 子串的插入
String InsStr(Sting s1,int i,String s2)
{
String str;
str.length = 0;
if(i <= 0 || i > s1.length + 1)
{
return str;
}
for(int j = 0;j < i-1;j++)
{
str.data[j] = s1.data[j];
}
for(int j = 0;j < s2.length;j++)
{
str.data[i+j-1] = s2.data[j];
}
for(int j = i-1;j < s1.length;j++)
{
str.data[s2.length+j] = s1.data[j];
}
str.length = s1.length + s2.length;
return str;
}2.1.7 子串的删除
String DelStr(String s,int i,int j)
{
Sting str;
str.length = 0;
if(i <= 0 || i > s.length || i+j > s.length+1)
{
return str;
}
for(int k = 0;k < i - 1;k++)
{
str.data[k] = s.data[k];
}
for(int k = i+j-1;k < s.length;k++)
{
str.data[k-j] = s.data[k];
}
str.length = s.length - j;
return str;
}2.1.8 子串的替换
String RepStr(String s,int i,int j,String t)
{
str.length = 0;
if (i <= 0;i > s.length || i+j-1 > s.length)
{
return str;
}
for(int k = 0;k < i - 1;k++)
{
str.data[k] = s.data[k];
}
for(int k = 0;k < t.length;k++)
{
str.data[i+k-1] = t.data[k];
}
for(int k = i+j-1;k < s.length;k++)
{
str.data[t.length+k-j] = s.data[k];
}
str.length = s.length - j + t.length;
return str;
}3. 字符串的模式匹配
给定一个子串 （模式串），要求在某个字符串 （目标串）中找出与该子串相同的所有子串。
3.1 Brute-Force算法
Brute-Force（暴力）简称BF算法，也称简单匹配算法，采用穷举方法。
基本思路是：将目标串 s 的第一个字符和模式串 t 的第一个字符比较，若相等，则继续逐个比较后续字符。否则从目标串s的下一个字符开始重新与模式串 t 的第一个字符比较。
void BF(String s,String t)
{
int i = 0,j = 0;
while(i < s.length && j < t.length)
{
if(s.data[i] == t.data[j])
{
i++;
j++;
}
else
{
i = i-j+1; //回退
j = 0;
}
}
if(j >= t.length)
{
printf("%d\t",i - t.length);
}
else
{
printf(-1);
}
}关于下面的KMP算法这位同学用图文详细的介绍了，很适合入门。链接地址
下面是我个人写的，非常简洁，有兴趣可以看一下
3.2 KMP算法
KMP算法的核心是匹配失败后分析模式串 t 从中提取出加速匹配的有用信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
3.2.1 从模式串 t 中提取有用信息
提取有用信息可让匹配失败后不再每次都只从目标串 s 的下一个字符开始，而是尽量多移几位而不发生匹配错误。
其求取公式：
| -1 j=0
next[j] = | MAX{k|0<K<j 且 "T0 T1… k-1"="Tj-k Tj-k…Tj-1"} 当匹配时
| 0 其他情况其算法：(有用信息存放next数组中)
void GetNext(String t,int next[])
{
int j = 0, k = -1;
next[0] = -1;
while(j < t.length - 1)
{
if(k == -1 || t.data[j] == t.data[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}3.2.2 KMP算法匹配过程
void KMP(String s,String t)
{
int next[MaxSize],i = 0,j = 0;
GetNext(t,next);
while(i < s.length && j < t.length)
{
if(j == -1 || s.data[i] == t.data[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(j >= t.length)
{
printf("%d\t",i - t.length);
}
else
{
printf(-1);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录