顺序串上的子串定位运算
子串定位又称串的模式匹配（Pattern Matching）或串匹配（String Matching）
在串匹配中一般将主串称为目标（串）子串称为模式（串）
假设T为目标串P为模式串且设
T=tt…tnP=pp…pm(＜m≤n)
用T[ij]表示T的子串titi+…tj(≤i≤j≤n)用P[ij]表示P的子串pipi+…pj(≤i≤j≤m)
串匹配实际上是对于合法的位置≤i≤nm依次将目标串中的子串T[ii+m]和模式串P[m]进行比较若T[ii+m]=P[m]（即titi+…ti+m=pp…pm）则称从位置i开始的匹配成功亦称模式P在目标T中出现若T[ii+m]≠P[m]（即存在某个≤j≤m使得ti+j≠pj）则称从位置i开始的匹配失败
上述的位置i又称为位移当T[ii+m]=p[m]时i称为有效位移当T[ii+m]≠p[m]时i称为无效位移
朴素的串匹配算法
基本思想用一个循环来依次检查nm+个合法的位移i（≤i≤nm）是否为有效位移
该算法至多匹配nm+次每匹配要做m次比较故算法至多比较m*(nm+)次时间复杂性为O((nm+)*m)通常情况下m的值远小于n的值时间复杂性可粗略地记为O(n*m)
链串上的子串定位运算
位移shift是结点地址而非整数且单链表中没有存储长度信息若匹配成功则返回有效位移所指的结点地址否则返回空指针
该算法的时间复杂度与顺序串上朴素的串匹配算法相同
