首页 > 试题广场 > 串的模式匹配
[编程题]串的模式匹配
  • 热度指数:13495 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于两个字符串A,B。请设计一个高效算法,找到B在A中第一次出现的起始位置。若B未在A中出现,则返回-1。

给定两个字符串AB,及它们的长度lenalenb,请返回题目所求的答案。

测试样例:
"acbc",4,"bc",2
返回:2

python只需要一行的解法:

return A.index(B) if B in A else -1
编辑于 2017-09-12 14:05:53 回复(3)
/*
第一种方法
*/
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;                        
    }
}

编辑于 2016-06-28 22:02:14 回复(2)
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;
    }
};

编辑于 2020-05-12 12:07:26 回复(0)
我想这题原本的意思是想考察KMP这类的模式匹配算法
但是
竟然没有禁用STL!
竟然没有禁用STL!
竟然没有禁用STL!

好吧,那我就无耻的这么做了
return A.find(B);

发表于 2016-08-28 20:36:53 回复(4)
//话说一年前我看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;
    }
};


编辑于 2017-04-10 20:39:41 回复(0)
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;
    }
};

发表于 2018-12-04 10:39:48 回复(1)
    int findAppearance(string A, int lena, string B, int lenb) {
        // write code here
        string::size_type pos = A.find(B);
        return pos;
    }

发表于 2017-05-06 15:17:42 回复(0)

import java.util.*;

public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        return A.indexOf(B);
    }
}
发表于 2016-04-22 23:31:48 回复(4)
    //这个错哪了?
    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;

发表于 2020-03-02 16:59:04 回复(0)
public class StringPattern {
    public int findAppearance(String A, int lena, String B, int lenb) {
        // write code here
        if(lena<lenb)
         return -1;
        return A.indexOf(B,0);
    }
}
发表于 2018-07-23 12:36:56 回复(3)
简单的不像话
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;
    }
}

发表于 2018-06-12 20:34:40 回复(0)
class StringPattern {
public:
    int findAppearance(string A, int lena, string B, int lenb) {
        if (lenb > lena||lenb<=0||lena<=0)
            return -1;
        int a,b;
        
        for (a = 0; a != lena; a++)
        {
            int t = a;
            b = 0;
            while (A[t] == B[b]&&b!=lenb)
            {
                t++, b++;
            }
            if (b == lenb)
                return a;
            
        }
        return -1;
    }
};
发表于 2018-04-16 17:23:34 回复(0)
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;
        }
    }
}

发表于 2018-04-12 17:57:44 回复(0)
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];         }     }
};

发表于 2017-10-11 01:35:48 回复(0)
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,写的有点麻烦了。。。

编辑于 2017-03-24 22:59:09 回复(0)
最简单的方法:使用STL算法,不过这种方法在面试时不吃香,毕竟体现不出逻辑分析过程。写完整算法过程,最好分A字符串和B字符串的长度大小比较情况进行编码。

发表于 2017-02-27 09:13:31 回复(0)
//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;
}
}
}

编辑于 2016-09-24 11:32:40 回复(0)
不要脸的直接用了函数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);
    }
} 

发表于 2016-08-28 21:55:23 回复(0)
/*
 * @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
}


发表于 2016-08-07 21:57:36 回复(0)
int k,h = 0;
int i;
for (i = 0; i <= lena - lenb; i++) {
             h = 0;
if (A.charAt(i) == B.charAt(0)) {
k = i;
for (int j = 0; j < lenb; j++) {
if (A.charAt(k) != B.charAt(j)) {
h = -1;
break;
}
k ++;
}
if (h == -1) {
continue;
}else {
h = 1;
break;
}
}
}
if (h == 1) {
return i;
}else {
return -1;
		}

发表于 2016-07-12 01:08:11 回复(0)