其實(shí)串這塊還是很簡單的幌缝，主要是kmp算法讓人頭大脆粥。考研書上基本都是c語言struct寫的，個人感覺還是用類寫比較清楚一些膏秫。
串的結(jié)構(gòu)定義
定長順序存儲表示
給串尾加上'\0'作為串結(jié)束的標(biāo)記。同時也設(shè)定length。這樣做雖然多用一個單位的存儲空間匣缘，但就是代碼中用起來最方便的形式澄成。
const int maxSize=99;
class Str{
public:
char str[maxSize+1];
int length;
};
串的動態(tài)分配存儲表示和重新賦值
#include <iostream>
using namespace std;
const int maxSize=99;
class Str{
public:
char *ch;
int length=0;
Str(char *c){
ch=c;
while(*c){
++length;
++c;
}
}
int reassign(char* c){
if(ch){
ch=NULL;
length=0;
int len=0;
char *temp;
temp=c;
while(*temp){
++len;
++temp;
}
if(len==0){ // 新字符串為空串
ch=NULL;
}else{
ch=c;
length=len;
}
return 1;
}
return 0;
}
};
int main(){
Str s("input");
s.reassign("hello world!!");
cout<<s.length; // 13
return 0;
}
串比較
有兩個串a(chǎn),b,如果a的ASCII碼小于b的ASCII碼，則返回a小于b標(biāo)記亭敢，如果a的ASCII碼大于b的ASCII碼滚婉，返回a大于b的標(biāo)記，如果a等于b的ASCII碼帅刀，則按照之前的規(guī)則繼續(xù)比較兩串中的下一對字符让腹。經(jīng)過上述步驟，在沒有比較出a和b大小的情況下扣溺，先結(jié)束的串為較小串骇窍。兩串同時結(jié)束，只要返回兩串相等標(biāo)記锥余。
int strCompare(Str s1,Str s2){
int i=0;
while(i<s1.length&&i<s2.length){
if(s1.ch[i]!=s2.ch[i]){
return s1.ch[i]-s2.ch[i];
}
i++;
}
return s1.length-s2.length;
}
int main(){
Str s("input1");
Str s1("input1");
int res=strCompare(s,s1);
cout<<res; // 0
}
串連接
如果a的ASCII碼小于b的ASCII碼腹纳，則返回a小于b標(biāo)記，如果a的ASCII碼大于b的ASCII碼驱犹，返回a大于b的標(biāo)記嘲恍，如果a等于b的ASCII碼，則按照之前的規(guī)則繼續(xù)比較兩串中的下一對字符雄驹。經(jīng)過上述步驟佃牛，在沒有比較出a和b大小的情況下，先結(jié)束的串為較小串医舆。兩串同時結(jié)束吁脱，只要返回兩串相等標(biāo)記。
int concat(Str &target,Str s1,Str s2){
if(target.ch){
target.ch=NULL;
}
target.ch=new char;
int i=0;
while(i<s1.length){
target.ch[i]=s1.ch[i];
i++;
}
int j=0;
while(j<s2.length){
target.ch[i+j]=s2.ch[j];
j++;
}
target.length=s1.length+s2.length;
return 1;
}
int main(){
Str s1("hello");
Str s2(" world");
Str target("");
concat(target,s1,s2);
cout<<target.length<<endl; // 11
}
求子串
從給定串中某一位置開始到某一位置結(jié)束的串的操作稱為求子串操作彬向。
int Str::substring(Str &str,int pos,int len){
if(str.ch){
str.ch=NULL;
}
if(pos+len>length){
cout<<"所求位置的字符串長度溢出"<<endl;
return 0;
}
str.ch=new char;
int i=0,j=0;
while(i<length){
if(i>=pos&&j<len){
str.ch[j]=ch[i];
j++;
}
i++;
}
str.length=len;
return 0;
}
int main(){
Str s1("hello");
Str s2(" world");
Str target("");
s1.substring(target,0,4);
target.readStr(); // hell
cout<<target.length<<endl; // 4
}
清空串
int Str::clearstring(){
if(ch){
ch=NULL;
}
length=0;
return 1;
}
int main(){
Str s1("hello");
s1.readStr(); //hello
s1.clearstring();
s1.readStr(); //
cout<<endl<<s1.length<<endl; // 0
}
串的模式匹配算法
1.簡單模式匹配的算法
基本思想從主串的第一個位置起和模式串的第一個字符開始比較兼贡，如果相等，則繼續(xù)逐一比較后續(xù)字符娃胆。否則從主串兒的第二個字符開始遍希，在重新用上一步的方法與模式串中的字符作比較，以此類推里烦，直到比較完成模式串中所有的字符凿蒜，若匹配成功禁谦，則返回串在主串中的位置，若匹配不成功废封，則返回一個可區(qū)別于主串所有位置的標(biāo)記州泊，如0。
int Str::indexOf(Str target){
if(length<target.length){
cout<<"invalid arguments"<<endl;
return -1;
}
int i=0,j=0,k=0;
while(i<length&&j<target.length){
if(ch[i]==target.ch[j]){
i++;
j++;
}else{
j=0;
i=++k;
}
}
if(j==target.length){
return k;
}
return -1;
}
int main(){
Str s1("hello");
cout<<s1.indexOf("8")<<endl; //-1
cout<<s1.indexOf("hel")<<endl; // 0
cout<<s1.indexOf("lo")<<endl; //3
}
2.kmp算法
kmp算法不好理解漂洋，總之重點(diǎn)是求出next數(shù)組遥皂，然后套用簡單匹配模式算法，將j的下一跳置為next[j]就ok了刽漂。具體的算法看博客是不好理解的演训，推薦大家去看視頻。我看的是b站一個印度小哥講解的贝咙，汪都能聽懂的KMP字符串匹配算法【雙語字幕】样悟，他的next數(shù)組與嚴(yán)蔚敏講解的不同，不過很好理解庭猩，我是看書真的看不懂了窟她，（我用19天勤的參考書，跑了遍程序發(fā)現(xiàn)是錯的ORZ）蔼水。下面的算法是拿js實(shí)現(xiàn)的礁苗，按照小哥思路寫的，和書上的next不一樣徙缴，需要你右移一位试伙，每位加1即為嚴(yán)的版本next。
求next數(shù)組
function getNextArr(str) {
let j = 0, i = 1;
const next = [0]
let isSuccessiveEqual = true;
while (i < str.length && j < str.length) {
if (str[j] == str[i]) {
next[i] = isSuccessiveEqual ? (next[i - 1] + 1) : next[j] + 1
i++
j++
isSuccessiveEqual = true
} else {
isSuccessiveEqual = false
if (j == 0) {
next[i] = 0
i++
} else {
j = next[j - 1]
}
}
}
return next
}
getNextArr('abcaby') // [0, 0, 0, 1, 2, 0]
getNextArr('aabaabaaa') // [0, 1, 0, 1, 2, 3, 4, 5, 2]
kmp算法
function kmp(text, pattern) {
const next = getNextArr(pattern)
let i = 0, j = 0
while (i < text.length && j < pattern.length) {
if (text[i] == pattern[j]) {
i++
j++
if (j == pattern.length) {
return i - pattern.length
}
} else {
j > 0 ? j = next[j - 1] : i++
}
}
return -1
}
kmp('abxabcabcaby', 'abcaby') // 6
kmp('111str111', 'str11') // 3
關(guān)注訂閱號獲得更加及時的推送~
