串：是由零个或多个字符组成的有限序列，又叫字符串。

串的抽象数据类型定义

  1. ADT String{
  2.     数据对象:D={a_i|a_i属于CharacterSet,i=1,2,...,n,n>=0}
  3.     数据关系:R_1={<a_i-1,a_i>|a_i-1,a_i属于D,1,2,...,n}
  4.     基本操作:
  5.     StrAssign(&T,chars)
  6.     初始条件:chars是字符串常量。
  7.     操作结果:生成一个其值等于chars的串T。
  8.     StrCopy(&T,S)
  9.     初始条件:串S存在。
  10.     操作结果:由串S复制得到串T。
  11.     StrEmpty(S)
  12.     初始条件:串S存在。
  13.     操作结果:若S为空串,则返回TRUE,否则返回FALSE。
  14.     StrCompare(S,T)
  15.     初始条件:串S和T存在。
  16.     操作结果:若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。
  17.     StrLength(S)
  18.     初始条件:串S存在。
  19.     操作结果:返回S的长度,称为串的长度。
  20.     ClearString(&S)
  21.     初始条件:串S存在。
  22.     操作结果:将S清为空串。
  23.     Concat(&T,S1,S2)
  24.     初始条件:串S1和S2存在。
  25.     操作结果:用T返回由S1和S2联接而成的新串。
  26.     SubString(&Sub,S,pos,len)
  27.     初始条件:串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1。
  28.     操作结果:用Sub返回串S第pos个字符起长度为len的字串。
  29.     Index(S,T,pos)
  30.     初始条件:串S和T存在,T是非空串,1<=pos<=StrLength(S)。
  31.     操作结果:若子串S中存在和串T值相同的字串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。
  32.     Replace(&S,T,V)
  33.     初始条件:串S,T和V存在,T是非空串。
  34.     操作结果:用V替主串S中出现的所有与T相等的不重叠的字串。
  35.     StrInsert(&S,pos,T)
  36.     初始条件:串S和T存在,1<=pos<=StrLength(S)+1。
  37.     操作结果:在串S的第pos个字符之前插入串T。
  38.     StrDelete(&S,pos,len)
  39.     初始条件:串S存在,1<=pos<=StrLength(S)-len+1。
  40.     操作结果:从串S中删除第pos个字符其起长度为len的字串。
  41.     DestroyString(&S)
  42.     初始条件:串S存在。
  43.     操作结果:串S被销毁。
  44. }ADT String;

串定长顺序存储表示

  1. #include "string.h"
  2. #include "stdio.h"    
  3. #include "stdlib.h"   
  5. #include "math.h"  
  6. #include "time.h"
  8. #define OK 1
  9. #define ERROR 0
  10. #define TRUE 1
  11. #define FALSE 0
  13. #define MAXSIZE 40 /* 存储空间初始分配量 */
  15. typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  16. typedef int ElemType;    /* ElemType类型根据实际情况而定，这里假设为int */
  18. typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */
  20. /* 生成一个其值等于chars的串T */
  21. Status StrAssign(String T,char *chars)
  22. { 
  23.     int i;
  24.     if(strlen(chars)>MAXSIZE)
  25.         return ERROR;
  26.     else
  27.     {
  28.         T[0]=strlen(chars);
  29.         for(i=1;i<=T[0];i++)
  30.             T[i]=*(chars+i-1);
  31.         return OK;
  32.     }
  33. }
  35. /* 由串S复制得串T */
  36. Status StrCopy(String T,String S)
  37. { 
  38.     int i;
  39.     for(i=0;i<=S[0];i++)
  40.         T[i]=S[i];
  41.     return OK;
  42. }
  44. /* 若S为空串,则返回TRUE,否则返回FALSE */
  45. Status StrEmpty(String S)
  46. { 
  47.     if(S[0]==0)
  48.         return TRUE;
  49.     else
  50.         return FALSE;
  51. }
  53. /*  初始条件: 串S和T存在 */
  54. /*  操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
  55. int StrCompare(String S,String T)
  56. { 
  57.     int i;
  58.     for(i=1;i<=S[0]&&i<=T[0];++i)
  59.         if(S[i]!=T[i])
  60.             return S[i]-T[i];
  61.     return S[0]-T[0];
  62. }
  64. /* 返回串的元素个数 */
  65. int StrLength(String S)
  66. { 
  67.     return S[0];
  68. }
  70. /* 初始条件:串S存在。操作结果:将S清为空串 */
  71. Status ClearString(String S)
  72. { 
  73.     S[0]=0;/*  令串长为零 */
  74.     return OK;
  75. }
  77. /* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */
  78. Status Concat(String T,String S1,String S2)
  79. {
  80.     int i;
  81.     if(S1[0]+S2[0]<=MAXSIZE)
  82.     { /*  未截断 */
  83.         for(i=1;i<=S1[0];i++)
  84.             T[i]=S1[i];
  85.         for(i=1;i<=S2[0];i++)
  86.             T[S1[0]+i]=S2[i];
  87.         T[0]=S1[0]+S2[0];
  88.         return TRUE;
  89.     }
  90.     else
  91.     { /*  截断S2 */
  92.         for(i=1;i<=S1[0];i++)
  93.             T[i]=S1[i];
  94.         for(i=1;i<=MAXSIZE-S1[0];i++)
  95.             T[S1[0]+i]=S2[i];
  96.         T[0]=MAXSIZE;
  97.         return FALSE;
  98.     }
  99. }
  101. /* 用Sub返回串S的第pos个字符起长度为len的子串。 */
  102. Status SubString(String Sub,String S,int pos,int len)
  103. {
  104.     int i;
  105.     if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
  106.         return ERROR;
  107.     for(i=1;i<=len;i++)
  108.         Sub[i]=S[pos+i-1];
  109.     Sub[0]=len;
  110.     return OK;
  111. }
  113. /* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
  114. /* 其中,T非空,1≤pos≤StrLength(S)。 */
  115. int Index(String S, String T, int pos) 
  116. {
  117.     int i = pos;    /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
  118.     int j = 1;                /* j用于子串T中当前位置下标值 */
  119.     while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
  120.     {
  121.         if (S[i] == T[j])     /* 两字母相等则继续 */
  122.         {
  123.             ++i;
  124.             ++j; 
  125.         } 
  126.         else                 /* 指针后退重新开始匹配 */
  127.         {  
  128.             i = i-j+2;        /* i退回到上次匹配首位的下一位 */
  129.             j = 1;             /* j退回到子串T的首位 */
  130.         }      
  131.     }
  132.     if (j > T[0]) 
  133.         return i-T[0];
  134.     else 
  135.         return 0;
  136. }
  139. /*  T为非空串。若主串S中第pos个字符之后存在与T相等的子串， */
  140. /*  则返回第一个这样的子串在S中的位置，否则返回0 */
  141. int Index2(String S, String T, int pos) 
  142. {
  143.     int n,m,i;
  144.     String sub;
  145.     if (pos > 0) 
  146.     {
  147.         n = StrLength(S);    /* 得到主串S的长度 */
  148.         m = StrLength(T);    /* 得到子串T的长度 */
  149.         i = pos;
  150.         while (i <= n-m+1) 
  151.         {
  152.             SubString (sub, S, i, m);    /* 取主串中第i个位置长度与T相等的子串给sub */
  153.             if (StrCompare(sub,T) != 0)    /* 如果两串不相等 */
  154.                 ++i;
  155.             else                 /* 如果两串相等 */
  156.                 return i;        /* 则返回i值 */
  157.         }
  158.     }
  159.     return 0;    /* 若无子串与T相等，返回0 */
  160. }
  163. /*  初始条件: 串S和T存在,1≤pos≤StrLength(S)+1 */
  164. /*  操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE */
  165. Status StrInsert(String S,int pos,String T)
  166. { 
  167.     int i;
  168.     if(pos<1||pos>S[0]+1)
  169.         return ERROR;
  170.     if(S[0]+T[0]<=MAXSIZE)
  171.     { /*  完全插入 */
  172.         for(i=S[0];i>=pos;i--)
  173.             S[i+T[0]]=S[i];
  174.         for(i=pos;i<pos+T[0];i++)
  175.             S[i]=T[i-pos+1];
  176.         S[0]=S[0]+T[0];
  177.         return TRUE;
  178.     }
  179.     else
  180.     { /*  部分插入 */
  181.         for(i=MAXSIZE;i<=pos;i--)
  182.             S[i]=S[i-T[0]];
  183.         for(i=pos;i<pos+T[0];i++)
  184.             S[i]=T[i-pos+1];
  185.         S[0]=MAXSIZE;
  186.         return FALSE;
  187.     }
  188. }
  190. /*  初始条件: 串S存在,1≤pos≤StrLength(S)-len+1 */
  191. /*  操作结果: 从串S中删除第pos个字符起长度为len的子串 */
  192. Status StrDelete(String S,int pos,int len)
  193. { 
  194.     int i;
  195.     if(pos<1||pos>S[0]-len+1||len<0)
  196.         return ERROR;
  197.     for(i=pos+len;i<=S[0];i++)
  198.         S[i-len]=S[i];
  199.     S[0]-=len;
  200.     return OK;
  201. }
  203. /*  初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */
  204. /*  操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */
  205. Status Replace(String S,String T,String V)
  206. { 
  207.     int i=1; /*  从串S的第一个字符起查找串T */
  208.     if(StrEmpty(T)) /*  T是空串 */
  209.         return ERROR;
  210.     do
  211.     {
  212.         i=Index(S,T,i); /*  结果i为从上一个i之后找到的子串T的位置 */
  213.         if(i) /*  串S中存在串T */
  214.         {
  215.             StrDelete(S,i,StrLength(T)); /*  删除该串T */
  216.             StrInsert(S,i,V); /*  在原串T的位置插入串V */
  217.             i+=StrLength(V); /*  在插入的串V后面继续查找串T */
  218.         }
  219.     }while(i);
  220.     return OK;
  221. }
  223. /*  输出字符串T */
  224. void StrPrint(String T)
  225. { 
  226.     int i;
  227.     for(i=1;i<=T[0];i++)
  228.         printf("%c",T[i]);
  229.     printf("\n");
  230. }
  233. int main()
  234. {
  236.     int i,j;
  237.     Status k;
  238.     char s;
  239.     String t,s1,s2;
  240.     printf("请输入串s1: ");
  242.     k=StrAssign(s1,"abcd");
  243.     if(!k)
  244.     {
  245.         printf("串长超过MAXSIZE(=%d)\n",MAXSIZE);
  246.         exit(0);
  247.     }
  248.     printf("串长为%d 串空否？%d(1:是 0:否)\n",StrLength(s1),StrEmpty(s1));
  249.     StrCopy(s2,s1);
  250.     printf("拷贝s1生成的串为: ");
  251.     StrPrint(s2);
  252.     printf("请输入串s2: ");
  254.     k=StrAssign(s2,"efghijk");
  255.     if(!k)
  256.     {
  257.         printf("串长超过MAXSIZE(%d)\n",MAXSIZE);
  258.         exit(0);
  259.     }
  260.     i=StrCompare(s1,s2);
  261.     if(i<0)
  262.         s='<';
  263.     else if(i==0)
  264.         s='=';
  265.     else
  266.         s='>';
  267.     printf("串s1%c串s2\n",s);
  268.     k=Concat(t,s1,s2);
  269.     printf("串s1联接串s2得到的串t为: ");
  270.     StrPrint(t);
  271.     if(k==FALSE)
  272.         printf("串t有截断\n");
  273.     ClearString(s1);
  274.     printf("清为空串后,串s1为: ");
  275.     StrPrint(s1);
  276.     printf("串长为%d 串空否？%d(1:是 0:否)\n",StrLength(s1),StrEmpty(s1));
  277.     printf("求串t的子串,请输入子串的起始位置,子串长度: ");
  279.     i=2;
  280.     j=3;
  281.     printf("%d,%d \n",i,j);
  283.     k=SubString(s2,t,i,j);
  284.     if(k)
  285.     {
  286.         printf("子串s2为: ");
  287.         StrPrint(s2);
  288.     }
  289.     printf("从串t的第pos个字符起,删除len个字符，请输入pos,len: ");
  291.     i=4;
  292.     j=2;
  293.     printf("%d,%d \n",i,j);
  296.     StrDelete(t,i,j);
  297.     printf("删除后的串t为: ");
  298.     StrPrint(t);
  299.     i=StrLength(s2)/2;
  300.     StrInsert(s2,i,t);
  301.     printf("在串s2的第%d个字符之前插入串t后,串s2为:\n",i);
  302.     StrPrint(s2);
  303.     i=Index(s2,t,1);
  304.     printf("s2的第%d个字母起和t第一次匹配\n",i);
  305.     SubString(t,s2,1,1);
  306.     printf("串t为：");
  307.     StrPrint(t);
  308.     Concat(s1,t,t);
  309.     printf("串s1为：");
  310.     StrPrint(s1);
  311.     Replace(s2,t,s1);
  312.     printf("用串s1取代串s2中和串t相同的不重叠的串后,串s2为: ");
  313.     StrPrint(s2);
  316.     return 0;
  317. }

输出

  1. 请输入串s1: 串长为4 串空否？0(1:是 0:否)
  2. 拷贝s1生成的串为: abcd
  3. 请输入串s2: 串s1<串s2
  4. 串s1联接串s2得到的串t为: abcdefghijk
  5. 清为空串后,串s1为: 
  6. 串长为0 串空否？1(1:是 0:否)
  7. 求串t的子串,请输入子串的起始位置,子串长度: 2,3         
  8. 子串s2为: bcd
  9. 从串t的第pos个字符起,删除len个字符，请输入pos,len: 4,2 
  10. 删除后的串t为: abcfghijk
  11. 在串s2的第1个字符之前插入串t后,串s2为:
  12. abcfghijkbcd
  13. s2的第1个字母起和t第一次匹配
  14. 串t为：a
  15. 串s1为：aa
  16. 用串s1取代串s2中和串t相同的不重叠的串后,串s2为: aabcfghijkbcd

串的堆分配存储表示

模式匹配KMP

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

KMP算法之求next数组代码讲解

点击查看【bilibili】
手算next数组
image.png
逐步推演

image.png
添加一个字符next[7]
image.png
公式推演
image.png

KMP_C代码

  1. #include "string.h"
  2. #include "stdio.h"    
  3. #include "stdlib.h"   
  5. #include "math.h"  
  6. #include "time.h"
  8. #define OK 1
  9. #define ERROR 0
  10. #define TRUE 1
  11. #define FALSE 0
  12. #define MAXSIZE 100 /* 存储空间初始分配量 */
  14. typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  15. typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
  17. typedef char String[MAXSIZE+1];/*  0号单元存放串的长度 */
  19. /* 生成一个其值等于chars的串T */
  20. Status StrAssign(String T,char *chars)
  21. { 
  22.     int i;
  23.     if(strlen(chars)>MAXSIZE)
  24.         return ERROR;
  25.     else
  26.     {
  27.         T[0]=strlen(chars);
  28.         for(i=1;i<=T[0];i++)
  29.             T[i]=*(chars+i-1);
  30.         return OK;
  31.     }
  32. }
  34. Status ClearString(String S)
  35. { 
  36.     S[0]=0;/*  令串长为零 */
  37.     return OK;
  38. }
  40. /*  输出字符串T。 */
  41. void StrPrint(String T)
  42. { 
  43.     int i;
  44.     for(i=1;i<=T[0];i++)
  45.         printf("%c",T[i]);
  46.     printf("\n");
  47. }
  49. /*  输出Next数组值。 */
  50. void NextPrint(int next[],int length)
  51. { 
  52.     int i;
  53.     for(i=1;i<=length;i++)
  54.         printf("%d",next[i]);
  55.     printf("\n");
  56. }
  58. /* 返回串的元素个数 */
  59. int StrLength(String S)
  60. { 
  61.     return S[0];
  62. }
  64. /* 朴素的模式匹配法 */
  65. int Index(String S, String T, int pos) 
  66. {
  67.     int i = pos;    /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
  68.     int j = 1;                /* j用于子串T中当前位置下标值 */
  69.     while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
  70.     {
  71.         if (S[i] == T[j])     /* 两字母相等则继续 */
  72.           {
  73.             ++i;
  74.              ++j; 
  75.           } 
  76.           else                 /* 指针后退重新开始匹配 */
  77.           {  
  78.              i = i-j+2;        /* i退回到上次匹配首位的下一位 */
  79.              j = 1;             /* j退回到子串T的首位 */
  80.           }      
  81.     }
  82.     if (j > T[0]) 
  83.         return i-T[0];
  84.     else 
  85.         return 0;
  86. }
  88. /* 通过计算返回子串T的next数组。 */
  89. void get_next(String T, int *next) 
  90. {
  91.     int i,k;
  92.       i=1;
  93.       k=0;
  94.       next[1]=0;
  95.       while (i<T[0])  /* 此处T[0]表示串T的长度 */
  96.      {
  97.         if(k==0 || T[i]== T[k]) 
  98.         {
  99.               ++i;  
  100.             ++k;  
  101.             next[i] = k;
  102.         } 
  103.         else 
  104.             k= next[k];    /* 若字符不相同，则k值回溯 */
  105.       }
  106. }
  108. /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
  109. /*  T非空，1≤pos≤StrLength(S)。 */
  110. int Index_KMP(String S, String T, int pos) 
  111. {
  112.     int i = pos;        /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
  113.     int j = 1;            /* j用于子串T中当前位置下标值 */
  114.     int next[255];        /* 定义一next数组 */
  115.     get_next(T, next);    /* 对串T作分析，得到next数组 */
  116.     while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
  117.     {
  118.         if (j==0 || S[i] == T[j])     /* 两字母相等则继续，与朴素算法增加了j=0判断 */
  119.           {
  120.              ++i;
  121.              ++j; 
  122.           } 
  123.           else             /* 指针后退重新开始匹配 */
  124.                j = next[j];/* j退回合适的位置，i值不变 */
  125.     }
  126.     if (j > T[0]) 
  127.         return i-T[0];
  128.     else 
  129.         return 0;
  130. }
  132. /* 求模式串T的next函数修正值并存入数组nextval */
  133. void get_nextval(String T, int *nextval) 
  134. {
  135.       int i,k;
  136.       i=1;
  137.       k=0;
  138.       nextval[1]=0;
  139.       while (i<T[0])  /* 此处T[0]表示串T的长度 */
  140.      {
  141.         if(k==0 || T[i]== T[k])     /* T[i]表示后缀的单个字符，T[k]表示前缀的单个字符 */
  142.         {
  143.               ++i;  
  144.             ++k;  
  145.             if (T[i]!=T[k])      /* 若当前字符与前缀字符不同 */
  146.                 nextval[i] = k;    /* 则当前的j为nextval在i位置的值 */
  147.               else 
  148.                 nextval[i] = nextval[k];    /* 如果与前缀字符相同，则将前缀字符的 */
  149.                                             /* nextval值赋值给nextval在i位置的值 */
  150.         } 
  151.         else 
  152.             k= nextval[k];            /* 若字符不相同，则k值回溯 */
  153.       }
  154. }
  156. int Index_KMP1(String S, String T, int pos) 
  157. {
  158.     int i = pos;        /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
  159.     int j = 1;            /* j用于子串T中当前位置下标值 */
  160.     int next[255];        /* 定义一next数组 */
  161.     get_nextval(T, next);    /* 对串T作分析，得到next数组 */
  162.     while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
  163.     {
  164.         if (j==0 || S[i] == T[j])     /* 两字母相等则继续，与朴素算法增加了j=0判断 */
  165.           {
  166.              ++i;
  167.              ++j; 
  168.           } 
  169.           else             /* 指针后退重新开始匹配 */
  170.                j = next[j];/* j退回合适的位置，i值不变 */
  171.     }
  172.     if (j > T[0]) 
  173.         return i-T[0];
  174.     else 
  175.         return 0;
  176. }
  178. int main()
  179. {
  180.     int i,*p;
  181.     String s1,s2;
  183.     StrAssign(s1,"abcdex");
  184.     printf("子串为: ");
  185.     StrPrint(s1);
  186.     i=StrLength(s1);
  187.     p=(int*)malloc((i+1)*sizeof(int));
  188.     get_next(s1,p); 
  189.     printf("Next为: ");
  190.     NextPrint(p,StrLength(s1));
  191.     printf("\n");
  193.     StrAssign(s1,"abcabx");
  194.     printf("子串为: ");
  195.     StrPrint(s1);
  196.     i=StrLength(s1);
  197.     p=(int*)malloc((i+1)*sizeof(int));
  198.     get_next(s1,p); 
  199.     printf("Next为: ");
  200.     NextPrint(p,StrLength(s1));
  201.     printf("\n");
  203.     StrAssign(s1,"ababaaaba");
  204.     printf("子串为: ");
  205.     StrPrint(s1);
  206.     i=StrLength(s1);
  207.     p=(int*)malloc((i+1)*sizeof(int));
  208.     get_next(s1,p); 
  209.     printf("Next为: ");
  210.     NextPrint(p,StrLength(s1));
  211.     printf("\n");
  213.     StrAssign(s1,"aaaaaaaab");
  214.     printf("子串为: ");
  215.     StrPrint(s1);
  216.     i=StrLength(s1);
  217.     p=(int*)malloc((i+1)*sizeof(int));
  218.     get_next(s1,p); 
  219.     printf("Next为: ");
  220.     NextPrint(p,StrLength(s1));
  221.     printf("\n");
  223.     StrAssign(s1,"ababaaaba");
  224.     printf("   子串为: ");
  225.     StrPrint(s1);
  226.     i=StrLength(s1);
  227.     p=(int*)malloc((i+1)*sizeof(int));
  228.     get_next(s1,p); 
  229.     printf("   Next为: ");
  230.     NextPrint(p,StrLength(s1));
  231.     get_nextval(s1,p); 
  232.     printf("NextVal为: ");
  233.     NextPrint(p,StrLength(s1));
  234.     printf("\n");
  236.     StrAssign(s1,"aaaaaaaab");
  237.     printf("   子串为: ");
  238.     StrPrint(s1);
  239.     i=StrLength(s1);
  240.     p=(int*)malloc((i+1)*sizeof(int));
  241.     get_next(s1,p); 
  242.     printf("   Next为: ");
  243.     NextPrint(p,StrLength(s1));
  244.     get_nextval(s1,p); 
  245.     printf("NextVal为: ");
  246.     NextPrint(p,StrLength(s1));
  248.     printf("\n");
  250.     StrAssign(s1,"00000000000000000000000000000000000000000000000001");
  251.     printf("主串为: ");
  252.     StrPrint(s1);
  253.     StrAssign(s2,"0000000001");
  254.     printf("子串为: ");
  255.     StrPrint(s2);
  256.     printf("\n");
  257.     printf("主串和子串在第%d个字符处首次匹配（朴素模式匹配算法）\n",Index(s1,s2,1));
  258.     printf("主串和子串在第%d个字符处首次匹配（KMP算法） \n",Index_KMP(s1,s2,1));
  259.     printf("主串和子串在第%d个字符处首次匹配（KMP改良算法） \n",Index_KMP1(s1,s2,1));
  261.     return 0;
  262. }

输出

  1. 子串为: abcdex
  2. Next为: 011111
  4. 子串为: abcabx
  5. Next为: 011123
  7. 子串为: ababaaaba
  8. Next为: 011234223
  10. 子串为: aaaaaaaab
  11. Next为: 012345678
  13.    子串为: ababaaaba
  14.    Next为: 011234223
  15. NextVal为: 010104210
  17.    子串为: aaaaaaaab
  18.    Next为: 012345678
  19. NextVal为: 000000008
  21. 主串为: 00000000000000000000000000000000000000000000000001
  22. 子串为: 0000000001
  24. 主串和子串在第41个字符处首次匹配（朴素模式匹配算法）
  25. 主串和子串在第41个字符处首次匹配（KMP算法）
  26. 主串和子串在第41个字符处首次匹配（KMP改良算法）