Are we expected to use KMP for this problem?


  • 12
    J

    Is it the standard string matching problem? Am I wrong?


  • 0
    P

    It is definitely solvable using KMP


  • 8

    No, it is not expected to use KMP for this problem. But it is a good exercise for those who are interested.


  • 4
    W

    There is a useful thread created by 1337 years back.
    http://leetcode.com/2010/10/implement-strstr-to-find-substring-in.html


  • 1
    W

    @1337, please consider to break this strStr problem into two problems. The second problem (strStr II) can add a complexity constraint.


  • 2
    L

    You can use KMP to solve it, but actually it is expected to use optimized brute-force search(i got AC use such one), just take care about several tricky cases if you got TLE result.


  • 3
    S

    just for reference,KMP + the trick mentioned in 1337's post

    class Solution {
    public:
        char *strStr(char *S, char *T) {
            if(!S||!T)return NULL;
            if(!*T)return S;
            int Plen = strlen(T);
            int *next = new int[Plen+1];
            initKMP(T,next,Plen);
            int i=0,j = 0;//i for S,j for T
            for(i=0;j<Plen&&*(S+i);){
                if(S[i]==T[j]){
                    i++;j++;
                }else if(next[j]>=0){
                    j = next[j];
                }else{
                    i++;
                    j = 0;
                    if(!*(S+i+Plen-1))break;
                }
            }
            if(j>=Plen)return S+i-Plen;
            else return NULL;
        }
        
        void initKMP(char str[],int next[],int len){
            int i=0,j=-1;
            next[0] = -1;
            while(i<len){
                while(j>=0&&str[i]!=str[j])j = next[j];
                i++;j++;
                if(str[j]==str[i])next[i] = next[j];
                else next[i] = j;
            }
        }
    };
    

  • 5
    I

    I used Rabin-Karp algorithm and it is accepted.

    class Solution {
    public:
        char *strStr(char *haystack, char *needle) {
    		int lenT = 0;
    		int lenP = 0;
    		while (haystack[lenT] != '\0'){
    			++lenT;
    		}
    		while (needle[lenP] != '\0'){
    			++lenP;
    		}
    		const int base = 256;
    		const int prime = 127;
    		int h = 1;
    		for (int i = 0; i< lenP-1; ++i){
    			h = (h*base)%prime;
    		}
    		int hashP = 0;
    		int hashT = 0;
    		for (int j = 0; j<lenP;++j){
    			hashP = (base*hashP+needle[j])%prime;
    			hashT = (base*hashT+haystack[j])%prime;
    		}
    		for (int s = 0; s<=(lenT-lenP); ++s){
    			if (hashP == hashT){
    				if(isPattern(haystack+s, needle,lenP)) return (haystack+s);
    			}
    			if (s<(lenT-lenP)){
    				hashT = (base*(hashT-haystack[s]*h) + haystack[s+lenP])%prime;
    				if (hashT<0){
    					hashT +=prime;
    				}
    			}
    		}
    		return NULL;
        }
    	bool isPattern(char* haystack, char* needle, int m){
    		for (int i = 0; i<m; ++i){
    			if (haystack[i] != needle[i]){
    				return false;
    			}
    		}
    		return true;
    	}
    };

  • 6
    F

    simple implementation not using KMP

     char *strStr(char *haystack, char *needle) {
        int len = strlen(needle);
    	int len2 = strlen(haystack);
    	int n=0;
    	if(*needle){
    		while(haystack[n]){
    			int i,j;
    			for(i=0,j=len-1;i<=j && n+j < len2 ;i++,j--){
    				 if(*(haystack+n+i)!=*(needle+i) || *(haystack+n+j)!=*(needle+j))
    				 	break;
    			}
    			if(i>j)
    				return &haystack[n];
    			n++;
    		}
    		return NULL;
    	}else
    		return haystack;
            
    }

  • 3
    N

    Just another version with Rabin-Karp algorithm.

    public class Solution {
        long R = 31L;
    	long M = 10000000000000003L;
    	long RK; // R^(pattern.length) % M
    
    	public String strStr(String haystack, String needle) {
    		if (haystack == null || needle == null || haystack.length() < needle.length())
    		    return null;
    		if(needle.length() == 0)
    		    return haystack;
    
    		long target = hash(needle, 0, needle.length() - 1);
    		long hash = hash(haystack, 0, needle.length() - 1);
    
    		RK = 1;
    		for (int i = 0; i < needle.length(); i++) {
    			RK = (RK * R) % M;
    		}
    		RK %= M;
    
    		if (hash == target)
    			return haystack;
    		for (int i = 1; i <= haystack.length() - needle.length(); i++) {
    			long tmp = nextHash(hash, haystack.charAt(i - 1), haystack.charAt(i + needle.length() - 1));
    			if (tmp == target)
    				return haystack.substring(i);
    			hash = tmp;
    		}
    		return null;
    	}
    
    	long hash(String s, int start, int end) {
    		long sum = 0;
    		for (int i = start; i <= end; i++) {
    			sum = sum * R % M + (int) s.charAt(i) % M;
    		}
    		return sum % M;
    	}
    
    	long nextHash(long hash, char oldFirst, char next) {
    		long a = hash * R % M;
    		long b = next % M;
    		long c = oldFirst % M * RK % M;
    
    		return (a + b - c + M) % M;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.