字符串——算法系列

计算机上的非数值处理的对象基本上是字符串数据，所以很有必要专门学习一下串。

串的逻辑结构和线性表极为相似，区别在于串的数据对象约束为字符集。操作通常针对串的整体，如在串中查找某个子串。

串的最小操作集

• 串赋值
• 串比较
• 求串长
• 串联接
• 求子串

串的表示与实现

• 定长顺序存储表示
• 堆分配存储表示（实现存储长度的动态增长）
• 块链存储表示

串的模式匹配算法

基本的匹配代码

#include <stdio.h>
#include <stdlib.h>

int my_length(char* string)
{
    char * end = string;
    while(*end != '\0')
        end++;
    return end - string;
}    

int my_index(char *src,char *key)
{
    int i = 0;
    int j = 0;
    while(i <= my_length(src))
    {
        //比较子串
        if(src[i] == key[j])
        {
            i++,j++;
            if(j == my_length(key))
                break;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }    
    }    
    if(j == my_length(key))
    return i - j;
    else return 0;
}    

int main(int argc, char *argv[])
{
    char string[] = "ABCFAUIERLFDAABEDJKJLJLD";
    printf("%d\n",my_index(string,"ABCD"));
  system("PAUSE");    
  return 0;
}

 这种算法很容易理解，不过在最坏的情况下的复杂度为Ο(n*m),n和m分别为主串和子串的长度

下面是KMP改进算法的实现，主要思想是，不匹配时，主串的游标不回溯，而是用子串的next函数来确定下一步怎么做。