算法1

题解

暴力：
该算法思维比较简单（但也常被一些公司做为面试题），很容易分析出本算法的时间复杂度为O(n*m)，我们主要是把时间浪费在什么地方呢，相信，你已经看到上面的代码注释中有这么一句话：“指针回溯，重新开始匹配”，这句话的意思就是好比我们乘坐一辆火车已经离站好远了，后来火车司机突然对全部乘客说，你们搭错了列车，要换一辆火车。也就是说在咱们的字符串匹配中，本来已经比较到前面的字符去了，现在又要回到原来的某一个位置重新开始一个个的比较。这就是问题的时间浪费点。

在继续分析之前，咱们来思考这样一个问题：
为什么快排或者堆排序比直接的选择排序快？直接的选择排序，每次都是重复的比较数值的大小，每扫描一次，只得出一个最大（小值），再没有其它的结果信息能给下一次扫描带来便捷。我们看看快排，每扫一次，将数据按某一值分成了两边，至少有右边的数据都大于左边的数据，所以在比较的时候，下一次就不用比较了。再看看堆排序，建堆的过程也是O(n)的比较，但比较的结果得到了最大（小）堆这种三角关系，之后的比较就不用再每一个都需要比较了。
* 由上述思考，咱们总结出了一点优化的归律：
采用一种简单的数据结构或者方式，将每次重复性的工作得到的信息记录得尽量多，方便下一次做同样的工作，这样将带来一定的优化

(暴力枚举) $O(nm)$

int methods(char* s, char* p)
{
    int sLen = n;
    int pLen = m;

    int i = 0;
    int j = 0;
    while (i < m && j <m)
    {
        if (s[i] == p[j])
        {
            //如果当前字符匹配成功（即S[i] == P[j]），则i++，j++    
            i++;
            j++;
        }
        else
        {
            //如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0    
            i = i - j + 1;
            j = 0;
        }
    }
    //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
    if (j == m)
        return i - j;
    else
        return -1;

}

yxc 老师朴素解法：

for(int i=1;i<=n;i++)
   bool flag =true;
   for(int i=0;i<=m;i++){
       if(s[i]=p[j])
       {
           flag=false;
           break;
       }
   }

时间复杂度分析：o(m+n)

题解

解题步骤：
1.求next数组
2.在匹配
举个例子，举例说明下上述求next数组的方法。
S a b a b a b c
P a b a b c
S[4] != P[4]
    那么下一个和S[4]匹配的位置是k=2(也即P[next[4]])。此处的k=2也再次佐证了上文第3节开头处关于为了找到下一个匹配的位置时k的求法。上面的主串与模式串开头4个字符都是“abab”，所以，匹配失效后下一个匹配的位置直接跳两步继续进行匹配。
S a b a b a b c
P     a b a b c
匹配成功

P的next数组值分别为-1 0 -1 0 2

next数组各值怎么求出来的呢?
分以下五步：

初始化：i=0，j=-1；

i=1，j=0，进入循环esle部分，j=next[j]=next[0]=-1；进入循环的if部分，++i，++j，i=2，j=0，因为p[i]=p[j]=a,所以next[2]=next[0]=-1；i=2,j=0,由于p[i]=p[j],再次进入循环if部分，所以++i=3，++j=1,因为p[i]=p[j]=b,所以next[3]=next[1]=0；i=3,j=1,由于p[i]=p[j]=b,所以++i=4，++j=2,因为p[i]!=p[j],所以next[4]=2。

匹配：
开始匹配，直到P[3]！=S[3]，匹配失败；next[3]=0，所以P[0]继续与S[3]匹配，再次匹配失败；next[0]=-1，满足循环if部分条件j==-1，所以，++i，++j，主串指针下移一个位置，从P[0]与S[4]处开始匹配，最后j==plen，跳出循环，输出结果i-plen=4，算法结束。

C++ 代码

#include<iostream>

using namespace std;

const int N=100010;
char a[N],b[N];
int ne[N];
int  n,m;

int main(){
    cin>>n>>a+1>>m>>b+1;
    for(int i=2,j=0;i<=n;i++){
       while(j&&a[i]!=a[j+1])j=ne[j];
       if(a[i]==a[j+1])j++;
       ne[i]=j;

    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&b[i]!=a[j+1])j=ne[j];
        if(b[i]==a[j+1])j++;
        if(j==n){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}