字符串处理003

字符串处理003

打卡第三天，昨天有点事情没来得及写，今天就补上昨天的题目。今天是字符串kmp暴力算法和string函数库中的substr函数。

题目004 字符串的移位运算(kmp暴力算法)

题目分析：
关键点：
1.需要判断两个字符串 的长度大小。
2.需要枚举位置移动后的字符串。
3.利用判断暴力kmp匹配字符串。
代码如下：

#include 
#include 

using namespace std;
bool judge(string str, string st) // 暴力枚举判断字符串的位置
{
    for(int i = 0; i < str.size(); i ++ )
    {
        int j = 0;
        while(str[i] == st[j] && j < st.size())
        {
            i ++;
            j ++;
        }
        if(j == st.size())
        return true;
        i = i - j + 1;
    }
    return false;
}
int main()
{   
    string str, st;
    char c;
    cin >> str >> st;
    if(st.size() > str.size())
    swap(str, st);
    for(int i = 0; i < str.size(); i ++ )
    {
        c = str[0];
        for(int j = 0; j < str.size() - 1; j ++ )
        {
            str[j] = str[j + 1];
        }
        str[str.size() - 1] = c;
        if(judge(str,st))
        {
            cout << "true" << endl;
            return 0;
        }
    }
    cout << "false" << endl;
    return 0;
}

其实还可以换成字符串处理函数substr来处理枚举问题：

string st;
st = str.substr(1) + str[0]; 

substr函数的用法：

substr(pos, n); // 位置pos代表从第pos位置开始截取n个字符;

题目005 字符串乘方(循环节问题)

思路分析：
找到字符串的循环节即可。还要注意将循环节进行循环后需要和原来字符串进行比较。
代码如下：

//大致思路就是将字符串中循环的部分分离出来之后在进行合并与原字符串进行比较
//题目类型 字符串循环节题目
//时间复杂度 O(n^2)
#include 
#include 

using namespace std;

int main()
{
    string str;
    while(cin >> str && str != ".")
    {
        int len = str.size();
        for(int n = len; n; n --)
        {
            if(len % n == 0)
            {
                int m = len / n;
                string s;
                s = str.substr(0, m); 
                string t;
                for(int i = 0; i < n ;i ++ )
                t += s;
                if(t == str)
                {
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

函数实用上还是使用函数substr。需要注意一下的就是进行判断的只能是长度的公约数，这样可以减少循环的次数，降低时间消耗。