C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-07-31

class StringPattern {
public:
    
    vector<int>getnext(string& A)
    {
        int len=A.length();
        vector<int>ans(len,-1);
        int k=-1;
        int i=0;
        while(i<len-1)
        {
            if(k<0||A[i]==A[k])
            {
                i++;
                k++;
                if(A[i]==A[k])
                    ans[i]=ans[k];
                else
                    ans[i]=k;
            }
            else
                k=ans[k];
        }
        return ans;
    }
    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        
        vector<int>next=getnext(B);
        int i=0;
        int j=0;
        int ans=-1;
        while(i<lena&&j<lenb)
        {
            if(j<0||A[i]==B[j])
            {
                i++;
                j++;
            }
            else
                j=next[j];
            if(j==lenb)
                break;
        }
        return j==lenb?i-j:-1;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2022-05-16

class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        int i=0;
        int j=0;
        int prev=0;//上一次匹配的位置
        while(i<A.size()&&j<B.size())
        {
            if(A[i]==B[j])
            {
                i++;
                j++;
            }
            else
            {
                j=0;
                i=prev+1;
                prev=i;
            }
        }
        return j==B.size()?prev:-1;
    }
};