What's this algorithm's name?


  • 0
    Z

    Once I saw solutions with familiar algorithms,but I don't know the exact name
    It change the charactor match into numbers equality.

    the solution's time cost is nearly O(n),since compare isn't use often.

    class Solution {
    public:
    int strStr( char *haystack,char *needle )
    {
    const int bigprime = 2047;
    const int b = 256;
    if( *needle == '\0' )   return 0;
    int n = 0,lh = 0,ln = 0;
    char *p = haystack;
    while( *p++ != '\0' )   ++lh;
    p = needle;
    while( *p++ != '\0' )   ++ln;
    if( ln > lh )   return -1;
    int remain = 0,dest = 0,key = 1;   
    //find the value of needle,haystack after mode bigprime
    for( int i = 0;i < ln;++i ) {
        remain = ( b * remain + needle[i] ) % bigprime;
        dest = ( b * dest + haystack[i] ) % bigprime;
    }
    for( int i = 0;i < ln - 1;++i )
        key = ( key * b ) % bigprime;
    //after mode ,the value equal not absolutely mean the two match,so use BruteForce to ensure it
    if( remain == dest && compare( haystack,needle,0,ln ) )  return 0;
    for( int i = 0;i < lh - ln;++i ) {
        dest = ( ( dest - haystack[i] * key ) * b + haystack[i+ln] ) % bigprime;
        while( dest < 0 )   dest += bigprime;
        if( dest == remain && compare( haystack,needle,i+1,ln ) )  return i+1;
    }
    return -1;
    }
    bool compare( char *compare,char *needle,int x,int len )
    {
    for( int i = 0;i < len;++i )
        if( *(compare+x+i) != *(needle+i))  return false;
    return true;
    }
    };

  • 1
    K

Log in to reply
 

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