设主串S=“xxyxxxyxxxxyxyx”，模式串T=“xxyxy”。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？

设主串S=“xxyxxxyxxxxyxyx”，模式串T=“xxyxy”。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？
正确答案：朴素的模式匹配(Brute-Force)时间复杂度是O(m*n)，KMP算法有一定改进，时间复杂度达到O(m+n)。本题也可以采用从后面匹配的方法，即从右向左扫描，比较6次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较19次成功。