leetcode-28 Implement strStr()

題意: 做字符串比對,輸出第一個符合的位置

解法: 這題就是問KMP實現了,原理可看筆者先前文章

C++ code:

class Solution {
public:
    int index[100000];
    int pre[100000];
    int strStr(string haystack, string needle) {
          int target=haystack.size();
          int target1=needle.size();
          if(target1==0)
              return 0; 
          int q=-1;
          pre[0]=-1;
          for(int i=1;i<target1;i++)
          {
              while(needle[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(needle[i]==needle[q+1])
                  q++;
              pre[i]=q;
          }
          q=-1;
          for(int i=0;i<target;i++)
          {
              while(haystack[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(haystack[i]==needle[q+1])
              {
                  q++;
                  if(q==target1-1)
                      return i-target1+1;
              }
          }
          return -1;  
    }
};