# What's this algorithm's name?

• 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;
}
};``````

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