注：不足及错误请指正
+qq 1366963396 讨论
串（string）是由零个或多个字符组成的有限序列，又名叫字符串
//生成一个其值等于字符串常量chars的串T,即在头部添加长度
char* StrAssign(char* T, char* chars)
{
T[0] =strlen(chars);
for (int i = 1; i <= T[0]; i++)
{
T[i] = *(chars + i - 1);
}
return T;
}
//串S存在，由串S复制得串T
char* StrCopy(char* T, char* S)
{
for (int i = 0; i < S[0]; i++)
T[i] = S[i];
return T;
}
//串S存在，将串清空
void ClearString(char* S)
{
if (StringEmpty(S))
return;
S[0] = 0;
}
//若串S为空，返回True
bool StringEmpty(char* S)
{
if (S[0] == 0)
return true;
return false;
}
//返回串S的长度
int StrLength(char* S)
{
return S[0];
}
//比较两个字符串(S>T,返回>0;S<T,返回<0;S=0,返回0)
int Strcompare(char* S, char* T)
{
for (int i = 1; i <= S[0] && i <= T[0]; i++)
{
if (S[i] != T[i])
return S[i] - T[i];
}
return S[0] - T[0];
}
//连接成新串
char* Concat(char* T, char* S1, char* S2)
{
T[0] = S1[0] + S2[0];
for (int i = 1; i <= S1[0]; i++)
{
T[i] = S1[i];
}
for (int i = S1[0]+1; i <= T[0]; i++)
{
T[i] = S1[i-S1[0]];
}
return T;
}
//串S存在，用sub返回S的第pos个字符起长度为len的字串
char* SubString(char* Sub, char* S, int pos, int len)
{
if (pos<1 || pos>S[0] || len > S[0] - pos + 1)
return NULL;
Sub[0] = len;
for (int i = 1; i <=len; i++)
{
Sub[i] = S[i+pos-1];
}
return Sub;
}
//朴素的模式匹配算法
//串S和T存在，T是非空串，若主串S中存在和串T值相同的子串，则返回他在主串S中第pos个字符之后第一次出现的位置，否则返回0
int Index(char* S, char* T, int pos)
{
int n, m, i;
char Sub[20];
if (pos > 0)
{
n = StrLength(S);
m = StrLength(T);
i = pos;
while (i<=n-m+1)
{
SubString(Sub, S, i, m);
if (Strcompare(Sub, T)!= 0)
++i;
else
{
return i;
}
}
}
return 0;
}
//串S，T，V存在，T是非空串，用V替换主串S中所有与T相等的不重叠的子串
char* Replace(char* S, char* T, char* V)
{
if (StringEmpty(T))
return S;
int n = StrLength(S);
int m = StrLength(T);
int k = StrLength(V);
char sub[20];
for (int i = 1; i <= n-m; i++)
{
if (Strcompare(SubString(sub,S,i,m),T)==0)
{
StrDelete(S, i, m);//删除T
StrInsert(S, i, V);//插入V
i += StrLength(V);//在插入V后继续寻找相同字串
}
else
{
continue;
}
}
return S;
}
//串S和T存在，在串S的第pos个字符之前插入串T
char* StrInsert(char* S, int pos, char* T)
{
if (pos<1 || pos>S[0] + 1)
return S;
for (int i = S[0]; i >= pos; i--)//后移
S[i + T[0]] = S[i];
for (int i = pos; i < pos + T[0]; i++)//插入
{
S[i] = T[i - pos + 1];
};
S[0] = S[0] + T[0];
return S;
}
//串S存在，从串S中删除第pos个字符起长度为len的字符串
char* StrDelete(char* S, int pos, int len)
{
if (pos<1 || len<0 || pos>S[0]-len + 1)
return S;
for (int i = pos; i <=S[0]-len; i++)
S[i] = S[i + len];
S[0] -= len;
return S;
}
//输出字符串
void PrintString(char* S)
{
for (int i = 1; i <= S[0]; i++)
printf("%c ", S[i]);
printf("\n");
}
//模式匹配，不用串的操作，只用基本数组,与上面Index的效果一样
int Index(char* S,char* T,int pos)
{
int i=pos;//i用于主串S中当前位置下标
int j=i;//j用于指示子串T中当前位置下标
while(i<=S[0]&&j<=T[0])
{
if(S[i]==T[j])//两字符相等则继续
{
++i;
++j;
}
else//重新开始匹配
{
i=i-j+2;//i退回到上次匹配首位的下一位
j=1;//j退回到子串的首位
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}
KMP匹配算法
//计算子串T的next数组
void get_next(char* T, int* next)
{
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])//T[i]表示后缀，T[j]表示前缀
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];//字符不相同，j值回溯
}
}
}
KMP匹配算法改进
//求模式串T的next函数修正值并存入nextval
void get_nextval(char* T, int* nextval)
{
int i = 1, j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])
{
++i;
++j;
if (T[i] != T[j])//若当前字符与前缀字符不同，，则当前的j为nextval在i位置的值
nextval[i] = j;
else
nextval[i] = nextval[j];//若相同，则将前缀字符的nextval值赋给nextval在i位的值
}
else
{
j = nextval[j];//若字符不相同，则j值回溯
}
}
}
网友评论