计算机基础知识：串的模式匹配之求子串位置的定位函数

中公

推荐阅读： 2014公共基础知识题库| 行政能力测试复习资料| 2014年申论热点
【导语】在事业单位考试中，计算机专业知识的复习向来是考生复习备考阶段的一大重点，其中新都事业单位考试网为计算机基础知识的复习为考生提供知识点梳理，帮助考生备考!
在串匹配中，假设S为目标串，P为模式串：
S=‘s1s2...sn’ P=‘p1p2…pm’
串的匹配实际上是根据 1≤i≤n-m+1 依次将 S 的子串 S’[i..i+m-1] 和 P[1..m] 进行比较，若 S’[i..i+m-1] = P[1..m]，则称从位置i开始的匹配成功;反之，匹配失败。
上述的位置i又称为位移，
当S’[i..i+m-1] = P[1..m]时，i称有效位移;
当S’[i..i+m-1]≠ P[1..m]时，i称无效位移。
这样，串匹配问题可简化为是找出某给定模式串 P 在给定目标串 S 中出现的有效位移。
以上是新都事业单位考试网为考生梳理计算机基础知识点，供大家学习识记!