#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int flag= 0 ;
void search( char * pat, char * txt, int q)
{
int M = strlen ( pat) ;
int N = strlen ( txt) ;
int i, j;
int p = 0 ; // hash value for pattern
int t = 0 ; // hash value for txt
int h = 1 ;
// The value of h would be "pow(d, M-1)%q"
for ( i = 0 ; i < M- 1 ; i++ )
h = ( h* d) % q;
// Calculate the hash value of pattern and first window of text
for ( i = 0 ; i < M; i++ )
{
p = ( d* p + pat[ i] ) % q;
t = ( d* t + txt[ i] ) % q;
}
// Slide the pattern over text one by one
for ( i = 0 ; i <= N - M; i++ )
{
// Chaeck the hash values of current window of text and pattern
// If the hash values match then only check for characters on by one
if ( p == t )
{
/* Check for characters one by one */
for ( j = 0 ; j < M; j++ )
{
if ( txt[ i+ j] ! = pat[ j] )
break ;
}
if ( j == M) // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
flag= 1 ;
}
}
// Calulate hash value for next window of text: Remove leading digit,
// add trailing digit
if ( i < N- M )
{
t = ( d* ( t - txt[ i] * h) + txt[ i+ M] ) % q;
// We might get negative value of t, converting it to positive
if ( t < 0 )
t = ( t + q) ;
}
}
}
// Driver program to test above function
int main( )
{
int t;
scanf ( "%d" ,& t) ;
while ( t-- )
{
char a1[ 100000 ] ;
char a2[ 100000 ] ;
scanf ( "%s" ,a1) ;
scanf ( "%s" ,a2) ;
flag= 0 ;
int q= 101
search( a2, a1,q) ;
if ( flag== 1 )
printf ( "YES\n " ) ;
else
printf ( "NO\n " ) ;
}
return 0 ;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CiNpbmNsdWRlPHN0ZGxpYi5oPgppbnQgZmxhZz0wOwp2b2lkIHNlYXJjaChjaGFyICpwYXQsIGNoYXIgKnR4dCwgaW50IHEpCnsKICAgIGludCBNID0gc3RybGVuKHBhdCk7CiAgICBpbnQgTiA9IHN0cmxlbih0eHQpOwogICAgaW50IGksIGo7CiAgICBpbnQgcCA9IDA7ICAvLyBoYXNoIHZhbHVlIGZvciBwYXR0ZXJuCiAgICBpbnQgdCA9IDA7IC8vIGhhc2ggdmFsdWUgZm9yIHR4dAogICAgaW50IGggPSAxOwogIAogICAgLy8gVGhlIHZhbHVlIG9mIGggd291bGQgYmUgInBvdyhkLCBNLTEpJXEiCiAgICBmb3IgKGkgPSAwOyBpIDwgTS0xOyBpKyspCiAgICAgICAgaCA9IChoKmQpJXE7CiAgCiAgICAvLyBDYWxjdWxhdGUgdGhlIGhhc2ggdmFsdWUgb2YgcGF0dGVybiBhbmQgZmlyc3Qgd2luZG93IG9mIHRleHQKICAgIGZvciAoaSA9IDA7IGkgPCBNOyBpKyspCiAgICB7CiAgICAgICAgcCA9IChkKnAgKyBwYXRbaV0pJXE7CiAgICAgICAgdCA9IChkKnQgKyB0eHRbaV0pJXE7CiAgICB9CiAgCiAgICAvLyBTbGlkZSB0aGUgcGF0dGVybiBvdmVyIHRleHQgb25lIGJ5IG9uZSAKICAgIGZvciAoaSA9IDA7IGkgPD0gTiAtIE07IGkrKykKICAgIHsKICAgICAgICAKICAgICAgICAvLyBDaGFlY2sgdGhlIGhhc2ggdmFsdWVzIG9mIGN1cnJlbnQgd2luZG93IG9mIHRleHQgYW5kIHBhdHRlcm4KICAgICAgICAvLyBJZiB0aGUgaGFzaCB2YWx1ZXMgbWF0Y2ggdGhlbiBvbmx5IGNoZWNrIGZvciBjaGFyYWN0ZXJzIG9uIGJ5IG9uZQogICAgICAgIGlmICggcCA9PSB0ICkKICAgICAgICB7CiAgICAgICAgICAgIC8qIENoZWNrIGZvciBjaGFyYWN0ZXJzIG9uZSBieSBvbmUgKi8KICAgICAgICAgICAgZm9yIChqID0gMDsgaiA8IE07IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKHR4dFtpK2pdICE9IHBhdFtqXSkKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoaiA9PSBNKSAgLy8gaWYgcCA9PSB0IGFuZCBwYXRbMC4uLk0tMV0gPSB0eHRbaSwgaSsxLCAuLi5pK00tMV0KICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZmxhZz0xOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgICAKICAgICAgICAvLyBDYWx1bGF0ZSBoYXNoIHZhbHVlIGZvciBuZXh0IHdpbmRvdyBvZiB0ZXh0OiBSZW1vdmUgbGVhZGluZyBkaWdpdCwgCiAgICAgICAgLy8gYWRkIHRyYWlsaW5nIGRpZ2l0ICAgICAgICAgICAKICAgICAgICBpZiAoIGkgPCBOLU0gKQogICAgICAgIHsKICAgICAgICAgICAgdCA9IChkKih0IC0gdHh0W2ldKmgpICsgdHh0W2krTV0pJXE7CiAgICAgICAgICAgICAKICAgICAgICAgICAgLy8gV2UgbWlnaHQgZ2V0IG5lZ2F0aXZlIHZhbHVlIG9mIHQsIGNvbnZlcnRpbmcgaXQgdG8gcG9zaXRpdmUKICAgICAgICAgICAgaWYodCA8IDApIAogICAgICAgICAgICAgIHQgPSAodCArIHEpOyAKICAgICAgICB9CiAgICB9Cn0gCi8vIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb24KaW50IG1haW4oKQp7CiAgIGludCB0OwoJc2NhbmYoIiVkIiwmdCk7Cgl3aGlsZSh0LS0pCgl7CiAgIGNoYXIgYTFbMTAwMDAwXTsKICAgY2hhciBhMlsxMDAwMDBdOwogICBzY2FuZigiJXMiLGExKTsKICAgc2NhbmYoIiVzIixhMik7CiAgIGZsYWc9MDsKICAgaW50IHE9MTAxCiAgIHNlYXJjaChhMiwgYTEscSk7CiAgIGlmKGZsYWc9PTEpCiAgICBwcmludGYoIllFU1xuIik7CiAgICBlbHNlCiAgICBwcmludGYoIk5PXG4iKTsKCX0KICAgcmV0dXJuIDA7Cn0=
compilation info
prog.cpp: In function ‘void search(char*, char*, int)’:
prog.cpp:16:16: error: ‘d’ was not declared in this scope
h = (h*d)%q;
^
prog.cpp:21:14: error: ‘d’ was not declared in this scope
p = (d*p + pat[i])%q;
^
prog.cpp:49:18: error: ‘d’ was not declared in this scope
t = (d*(t - txt[i]*h) + txt[i+M])%q;
^
prog.cpp: In function ‘int main()’:
prog.cpp:70:4: error: expected ‘,’ or ‘;’ before ‘search’
search(a2, a1,q);
^
prog.cpp:69:8: warning: unused variable ‘q’ [-Wunused-variable]
int q=101
^
stdout