子字符串定位方法

#include
#include

int myf(char *src, char *sub) {
 int i,j, k;
 int m = strlen(sub);
 int n = strlen(src);
 
 
 for (i=0; i<=n-m; i++) {
  j=0; k = i;
  while (j < m && src[k] == sub[j]) {
   j++; k++;
  }
  
  
  if (j == m)
   return i;
  
 }
 return -1;
}

int main(){
 char src[21] = "1234578901234566890";
 char sub[3] = "66";
 
 int res = myf(src, sub);
 printf("%d\n",res);
 printf("%s\n","---------------------------------------"); 
 printf("%d\n", strlen(src));
 printf("%c\n", src[2]);
 printf("%s\n", sub);
 return 0;
}

                                                                                                                  

子串定位运算

    　串是特殊的线性表，故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似。
    　C语言的串库里提供了丰富的串函数来实现各种基本运算，因此我们对各种串运算的实现不作讨论。利用串函数实现串的基本运算部分内容【参见练习】。
    　下面讨论在顺序串和链串上实现的子串定位运算。

1、子串定位运算
    　子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。
 　　【例】在文本编辑中，我们经常要查找某一特定单词在文本中出现的位置。解此问题的有效算法能极大地提高文本编辑程序的响应性能。
   　子串定位运算又称串的模式匹配或串匹配。

2、目标（串）和模式（串）
    　在串匹配中，一般将主串称为目标（串），子串称为模式（串）。
    　假设T 为目标串，P为模式串，且不妨设：
              T="t0t1t2…tn-1"
              P="p0p1p2…pm-1"(0＜m≤n)

3、串匹配
    　串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串"titi+1…ti+m-1"和模式串"p0p1p2…pm-1"进行比较：
　　①若"titi+1…ti+m-1"＝"p0p1p2…pm-1"，则称从位置i开始的匹配成功，或称i为有效位移。
　　②若"titi+1…ti+m-1"≠"p0p1p2…pm-1"，则称从位置i开始的匹配失败，或称i为无效位移。
　　因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。
      注意：
　　有些应用中要求求出P在T中所有出现的有效位移。

4、顺序串上的子串定位运算
（1）朴素的串匹配算法的基本思想
    　即用一个循环来依次检查n-m+1个合法的位移i（0≤i≤n-m）是否为有效位移。
具体过程【参见动画演示】

（2）顺序串上的串匹配算法
    　以下以第二种定长的顺序串类型作为存储结构。给出串匹配的算法：
        #define MaxStrSize 256  //该值依赖于应用，由用户定义
       typedef struct{
            char ch[MaxStrSize]; //可容纳256个字符，并依次存储在ch[0..n]中
            int length;
        }SeqString;
         int Naive StrMatch(SeqString T,SeqString P)
         {//找模式P在目标T中首次出现的位置，成功返回第1个有效位移，否则返回-1
              int i,j,k;
              int m=P.length;  //模式串长度
              int n=T.length;  //目标串长度
              for(i=0;i<=n-m;i++){  //0<=i<=n-m是合法的位移
                  j=0;k=i;  //下面用while循环判定i是否为有效位移
                  while(j                           k++;j++;
                   }
                    if(j==m)  //既T[i..i+m-1]=P[0..m-1]
                          return i;  //i为有效位移，否则查找下一个位移
               }//endfor
               return -1;  //找不到有效位移，匹配失败
           }//NaiveStrMatch

（3）算法分析
①最坏时间复杂度
    　该算法最坏情况下的时间复杂度为O((n-m+1)m)。
  分析：当目标串和模式串分别是"an-1b"和"am-1b"时，对所有n-m+1个合法的位移，均要比较m个字符才能确定该位移是否为有效位移，因此所需比较字符的总次数为（n-m+1）m。

②模式匹配算法的改进
　    朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,…,0时的部分匹配结果。
    　若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在O（m+n）数量级上。具体可【参阅有关文献】。

5、链串上的子串定位运算
    　用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。具体算法如下：
      LinkStrNode *LinkStrMatch(LinkString T,LinkString P)
      {//在链串上求模式P在目标T首次出现的位置
         LinkStrNode * shift,*t,*p;
         shift=T;  //shift表示位移
         t=shift;p=P;
         while(t&&p)  {
                if(t->data==p->data){  //继续比较后续结点中字符
                     t=t->next;
                     p=p->next;
                }
                else{  //已确定shift为无效位移
                    shift=shift->next;  //模式右移，继续判定shift是否为有效位移
                    t=shift;
                    p=P;
                 }
          }//endwhile
          if(p==NULL)
             return shift;  //匹配成功
          else
             return NULL;  //匹配失败
      }

    　该算法的时间复杂度与顺序表上朴素的串匹配算法相同。