text: Check if the given string is shuffled substring of another string | This function returns true if contents of arr1 [ ] and arr2 [ ] are same , otherwise false . ; This function search for all permutations of pat [ ] in txt [ ] ; countP [ ] : Store count of all characters of pattern countTW [ ] : Store count of current window of text ; Traverse through remaining characters of pattern ; Compare counts of current window of text with counts of pattern [ ] ; Add current character to current window ; Remove the first character of previous window ; Check for the last window in text ; Driver program to test above function
code: #include <iostream> NEW_LINE #include <cstring> NEW_LINE #define MAX  256 NEW_LINE using namespace std ; bool compare ( char arr1 [ ] , char arr2 [ ] ) { for ( int i = 0 ; i < MAX ; i ++ ) if ( arr1 [ i ] != arr2 [ i ] ) return false ; return true ; } bool search ( char * pat , char * txt ) { int M = strlen ( pat ) , N = strlen ( txt ) ; char countP [ MAX ] = { 0 } , countTW [ MAX ] = { 0 } ; for ( int i = 0 ; i < M ; i ++ ) { ( countP [ pat [ i ] ] ) ++ ; ( countTW [ txt [ i ] ] ) ++ ; } for ( int i = M ; i < N ; i ++ ) { if ( compare ( countP , countTW ) ) return true ; ( countTW [ txt [ i ] ] ) ++ ; countTW [ txt [ i - M ] ] -- ; } if ( compare ( countP , countTW ) ) return true ; return false ; } int main ( ) { char txt [ ] = " BACDGABCDA " ; char pat [ ] = " ABCD " ; if ( search ( pat , txt ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }