c++ Rabin-Kaap 알고리즘을 활용한 leetcode 796번 Rotate String (O(N))

RotateString 문제는

abcde 같은 문자열을 cdeab와 같이 표현 할 수 있다.

두 문자가 움직여 졌을 때 같은 문자열로 변환될 수 있는지 구하는 것이다.

string 문제는 O(N)으로 풀어야 한다.

이중 for loop은 지양하도록 하자.

 

 

코드 >>

#include <iostream>
#include <string>
 
// C++ Rabin-Kaap 알고리즘으로 쉽게 구현
using namespace std;
class Solution {
public:
    bool rotateString (string s, string goal) {
        // 만약 문자의 길이가 다르면 바로 리턴한다.
        int goal_length = (int)goal.size();        
        if (s.size() != goal_length)
            return false;
        string double_s;
        double_s.reserve(200);
        double_s = s + s;
        int double_s_length = (int)double_s.size();
        hash<string> hash_func;
        for (int i = 0; i <= (double_s_length - goal_length); i++)
        {
            string temp = double_s.substr(i, goal_length);
            if (hash_func(temp) == hash_func(goal))
            {
                if (temp == goal)
                    return true;                
            }
        }
 
        return false;
    };
};
 
int main()
{
    Solution solution = Solution();
    string s = "abcde";
    //string goal = "cdeab";
    string goal = "abced";
    bool match = solution.rotateString(s, goal);
 
    std::cout << match << std::endl;
 
    return 0;
}