matrix string match

Given a puzzle of letters/ characters e.g.
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.
Find the signature (sorting by alphabet) for each row and each column, put them on the hashtable where the key is signature and the value is corresponding row or column O(n*n)
Get signature of input string and look up the hashtable O(1)
After we locate the row or column, we can do the string match on the row/column with input string O(n)

the problem of finding the number of different cyclic shifts of a string that results in the same string

the problem of finding the number of different cyclic shifts of a string that results in the same string
For abab the answer is 2: cyclic shift at index 0 and 2
string ss = str+str; //str is the input
int ans = str.size()/ss.find(str, 1); //ans is the reqd answer