Hash Java Solution


  • 0
    2
    public int strStr(String haystack, String needle)
    {
    	int n=haystack.length();
    	int m=needle.length();
    	if(m<1) return 0;
    	if(n<1||m>n) return -1;
    	
    	long Q=BigInteger.probablePrime(31, new Random()).longValue();
    	long RM=1;
    	for(int i=1;i<=m-1;i++)
    		RM=(256*RM)%Q;
    	long pathash=0;
    	for(int j=0;j<m;j++)
    		pathash=(256*pathash+needle.charAt(j))%Q;
    	//search
    
    	long txtHash=0;
    	for(int j=0;j<m;j++)
    		txtHash=(256*txtHash+haystack.charAt(j))%Q;
    	
    	if(pathash==txtHash) return 0;
    	for(int i=m;i<n;i++)
    	{
    		txtHash=(txtHash+Q-RM*haystack.charAt(i-m)%Q)%Q;
    		txtHash=(txtHash*256+haystack.charAt(i))%Q;
    		
    		if(txtHash==pathash) return i-m+1;
    	}
    	
    	return -1;
    }

Log in to reply
 

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