串的模式匹配

python只需要一行的解法：

return A.index(B) if B in A else -1

class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        // 不建议暴力求解，掌握KMP多好
        // 考察基本的KMP字符匹配算法，时间复杂度相当好O(n)
        return kmp(A, B);
    }
    
    int kmp(const string& t, const string& str)
    {
        int n = t.length();
        int m = str.length();
        if (n < m)
            return -1;
        vector<int> pre(m, 0);
        int k = 0;
        for (int i = 1; i < m; ++i)
        {
            while (k > 0 && str[k] != str[i])
                k = pre[k];
            if (str[i] == str[k])
                k += 1;
            pre[i] = k;
        }
        int q = 0;
        for (int i = 0; i < n; ++i)
        {
            while (q > 0 && t[i] != str[q])
                q = pre[q];
            if (t[i] == str[q])
                q += 1;
            if (q == m)
                return i - m + 1;
        }
        return -1;
    }
};

return A.find(B);

/*
第一种方法
*/
import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        // write code here
     
        int result=A.indexOf(B);
        return result;
    }
}

/*第二种方法*/
import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {           
       //判断长度
       // char[] ch1=A.toCharArray();
       //char[] ch2=B.toCharArray();
        if(lena<lenb)
            return -1;
        if(lena==lenb)
        {
            if(A.equals(B))
                return 0;
            else
                return -1 ;           
        }
        
        //lena>lenb
        //截取字符串。
        //遍历一遍，记录B字符串首字符出现的位置
        int i=0;
        while(i<=lena-lenb)
         {
           // if(ch1[i]==ch2[0])
            if(A.charAt(i)==B.charAt(0))
            {
                String temp=A.substring(i,i+lenb);
                if(temp.equals(B))
                    return i;
                else
                 {
                    i++;
                    continue;
                }                
            }            
            i++;                        
        }        
        return -1;                        
    }
}

//话说一年前我看KMP算法被虐的生活不能自理
//如今秒懂
//不过去年学的python，今年重新投入C++的怀抱
//看来python只是适合上手，学算法啥的还是C++清晰明了
class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        return kmp(A.c_str(), lena, B.c_str(), lenb);
    }
private:
    //next 
    static void compute_prefix(const char *pattern, int next[]) {
        int i;
        //j表示既是自身真后缀又是最长前缀的字符串长度
        int j = -1;
        const int m = strlen(pattern);

        next[0] = j;
        for (i = 1; i < m; i++) {
            //失配的操作
	    //递归调用next，直到整个pattern再无最长前缀或者找到一个之前的满足条件的最长前缀
            while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];

            if (pattern[i] == pattern[j + 1])  j++;
            next[i] = j;
        }
    }

    //kmp
    static int kmp(const char *text, int m, const char *pattern, int n) {
        int i;
        int j = -1;
        //const int m = strlen(text);
        //const int n = strlen(pattern);

        int *next = new int[n];

        compute_prefix(pattern, next);

        for (i = 0; i < m; i++) {
            while (j > -1 && pattern[j + 1] != text[i]) j = next[j];

            if (text[i] == pattern[j + 1]) j++;

            if (j == n - 1) {
                //记得delete
                delete []next;
                return i - j;
            }
        }
        delete []next;
        return -1;
    }
};

class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        if(lenb > lena)
            return -1;
        if(lenb == 0)
            return 0;
        int j = 0;
        for(int i = 0; i < lena;i++)
        {
            if(A[i] == B[j])
                j++;
            else
                j = 0;
            if( j == lenb )
                return i - j + 1;
        }
        return -1;
    }
};

    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        string::size_type pos = A.find(B);
        return pos;
    }

    //这个错哪了？
    if(lena<lenb)
            return -1;
        if(lena==lenb)
        {
            if(strcmp(A.c_str(),B.c_str())==0)
                return 0;
            else
                return -1;
        }
        int i = 0;
        while(i<=(lena-lenb))
        {
            if(A[i]==B[0])
            {
                string temp = A.substr(i,i+lenb);
                if(strcmp(temp.c_str(),B.c_str())==0)
                {
                    return i;
                }
                else
                {
                    i++;
                    continue;
                }
            }
            i++;
        }
        return -1;

import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        // write code here
        for(int i=0; i<=lena-lenb; i++){
            if(A.substring(i, i+lenb).equals(B.substring(0,lenb)))
                return i;
        }
        return -1;
    }
}

import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        char[] charA = A.toCharArray();
        char[] charB = B.toCharArray();
        int i = 0;
        int j = 0;
        while (i < lena && j < lenb) {
            if(charA[i] == charB[j]){
                i++;
                j++;
            } else {
                i = i - (j -1);
                j = 0;
            }
            
        }
        
        if(j == lenb) {
            return i - j;
        } else {
            return -1;
        }
    }
}

class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        vector<int> next(lenb,0);
        getNext(next, B);
        int i=0,j=0;
        while(i<lena && j<lenb)
        {
            if(j==-1 || A[i]==B[j]){
                i++;
                j++;             }else                 j = next[j];         }         if(j == lenb)             return i-j;         else             return -1;
    }
    void getNext(vector<int> &next, const string s){
        int l = s.length();
        next[0] = -1;
        int k=-1,i=0;
        while(i < l-1){
            if(k==-1 || s[i]==s[k])
            {
                if(s[++i] == s[++k])
                    next[i] = next[k];
                else
                    next[i] = k;             }else                 k = next[k];         }     }
};

public int findAppearance(String A, int lena, String B, int lenb) {
    	char[] AA = A.toCharArray();
    	char[] BB = B.toCharArray(); 
    	int f = -1;
    	int b = 0;
    	if(lena>=lenb){
			for(int a=0;a<lena;a++){
				while(b<lenb){
    				if(BB[b]!=AA[a]){
    					if((lena-a)<=(lenb-b)){//若剩余的a字符数组小于b数组
    						return -1;
    					}
    					if(f<0){
    						break;
    					}else{
	    					if(BB[0]==AA[a]){
	    						f=a;
	    						if(lenb==1){
	        						return f;
	        					}
	    						b=1;
	    					}else{
	    						b=0;
	    					}
	    					break;
    					}
    				}
    				if(BB[b]==AA[a]){
    					f=a;
    					if(b==(lenb-1)){
    						return f-lenb+1;
    					}
    					b++;
    					break;
    				}
    			}
    		}
    	}
	return -1;
    }

35ms,709k,写的有点麻烦了。。。

最简单的方法：使用STL算法，不过这种方法在面试时不吃香，毕竟体现不出逻辑分析过程。写完整算法过程，最好分A字符串和B字符串的长度大小比较情况进行编码。

//KMP匹配算法
import java.util.*;
public class StringPattern {
public int findAppearance(String A, int lena, String B, int
  lenb) {
// write code here
return kmp(A,lena,B,lenb);
}
public int kmp(String A,int lena,String B,int lenb){
if(A==null||B==null||lena==0||lenb==0)
return -1;
int[] next = new int[lenb];
makenext(B,next);
int j = 0;
for(int i=0;i<lena;i++){
while(j>0&&A.charAt(i)!=B.charAt(j))
j = next[j-1];
if(A.charAt(i)==B.charAt(j))
j++;
if(j==lenb)
return i-j+1;
}
return -1;
}
public void makenext(String B,int[] next){          
   //创建next表
next[0] = 0;
int j = 0;
for(int i=1;i<B.length();i++){
while(j>0&&B.charAt(i)!=B.charAt(j))
j = next[j-1];
if(B.charAt(i)==B.charAt(j))
j++;       
next[i] = j;
}
}
}

不要脸的直接用了函数indexOf() import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        // write code here
        return A.indexOf(B);
    }
} 

/*
 * @description 字符串匹配的KMP算法；
 * @author snow
 * @time 2016-08-07 21:45
 * @算法思想：字符串匹配逐项匹配时间复杂度过高，使用KMP算法时间复杂度为O(N);
 *        每次不用再退回主串进行匹配，模式串返回的位置有最优解，提高了查询效率；
 */
public class StinrgFitKMP {

	   
	   private static int getSubIndex(char[] cs,char[] ct){
		   int next[] = new int[ct.length];
		   int j=0,k=0;
		   next = setNext(next,ct);
		   for(;k<cs.length;k++){
			    if(j==ct.length)
			    	break;
			   	if(cs[k]==(ct[j])){
			   		j++;
			   	}else if(j!=0){
			   		j = next[j];
			   		k--;
			   	}
		   }//for end
		   if(k==cs.length&&j!=ct.length)
			   return -1;
		   return k-j;
	   }//getSubIndex() end
	//设置next数组，以备出现不匹配时进行字符跳转
	private static int[] setNext(int[] next, char[] ct) {
		next[0] = 0;
		if(ct.length>1){
			next[1] = 0;       
			for(int i=2;i<ct.length;i++){
				int p = next[i-1];
				/* 
				 *     检测i这个位置的前一个信息和next对应的信息；
				 *     相同，则将高处存储为对应的上边的下一个位置；
				 *     不同，则应该只返回上一个对应的位置；
				 * 
				 */
				while(true){					 //虽然嵌套了循环，但是模式串短，并且循环次数和模式串的长度不是同一个数量级，不会影响到时间复杂度的数量级
					if(p==0||ct[i-1]==ct[p]){
						next[i] =  p + 1;
						break;
					}else{
						 p = next[p];			//出现不同，又不是起点，从上一个相关处回执
					}
				}//while end
			}//for end
	    }//if end
		return next;
	}//setNext() end
}

		}