codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
//By momo #include<cstdio> #include<algorithm> using namespace std; int p[10100], t; char a[10100], b[10100]; int main(){ scanf( "%d", &t ); while( t-- ){ scanf( "%s%s", a, b ); int L = strlen(a), l = strlen(b), cnt = 0; int k = p[0] = -1; for( int i = 1 ; i < l ; i++ ){ while( k >= 0 && b[k+1] != b[i] ) k = p[k]; if( b[k+1] == b[i] ) k++; p[i] = k; } k = -1; for( int i = 0 ; i < L ; i++ ){ while( k >= 0 && b[k+1] != a[i] ) k = p[k]; if( b[k+1] == a[i] ) k++; if( k == l-1 ){ cnt++; k = p[k]; } } printf( "%d\n", cnt ); } } }
Private
[
?
]
Run code
Submit