牛牛与字符串5

牛牛有两个环形字符串s1和s2，他想知道它们是否有可能是同一个字符串，如果是，返回"YES"，反之，返回"NO"。

题解：此题如果用排序，然后去判断，复杂度为nlogn，时间不允许。但是我们可以分别求出两个字符串的最小表示法，再循环比较判断是否相等。
时间复杂度：O(n)
空间复杂度：O(1)
参考代码如下:

class Solution {
public:
    int getmin(string s)
    {
        int n = s.size();
        int i = 0, j = 1, k = 0, t;

        while (i < n && j < n && k < n)
        {
            t = s[(i + k) % n] - s[(j + k) % n];

            if (!t)
                k++;
            else
            {
                if (t > 0)
                    i += k + 1;
                else
                    j += k + 1;
                if (i == j)
                    j++;
                k = 0;
            }
        }
        return i > j ? j : i;
    }

    string solve(string s1, string s2)
    {
        int n = s1.size();
        int m = s2.size();
        if (n != m)
        {
            return "NO";
        }
        int a = getmin(s1);
        int b = getmin(s2);

        for (int i = 0; i < n; i++)
            if (s1[(a + i) % n] != s2[(b + i) % n])
            {
                return "NO";
            }

        return "YES";
    }
};