每日算法刷题Day9-字符串移位包含问题、字符串乘方

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

29.字符串移位包含问题

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串 s1 和 s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。

例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。

输入格式

共一行，包含两个字符串，中间由单个空格隔开。

字符串只包含字母和数字，长度不超过 30。

输出格式

如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出 true，否则输出 false。

输入样例：

AABCD CDAA

输出样例：

true

思路

这里我们要学会暴力枚举的方法。

整体思路如下：首先要确定下两个字符串的长度关系，我们将长的字符串依次移位，短字符串去对应，如果对应成功则true反之false。伪代码如下：

for(   )
{
	通过当前循环移位得到a`
	判断b是否是a`的子集
		for（起点）
			for（枚举对应位置的字符）
}

代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string a,b;
    cin >>a>>b;
    
    if(a.size()<b.size())swap(a,b);
    
    for(int i = 0; i < a.size(); i++)
    {
        //进行位移
        a = a.substr(1) + a[0];
        //逐位比较b与a`
        for(int j = 0 ; j + b.size() <= a.size();j++)//外循环：起点
            {
                int k = 0;
            	//内循环：对应位置
                for(; k < b.size(); k++)
                    if(a[j + k] != b[k])break;
                if( k == b.size())
                {
                    puts("true");
                    return 0;
                }
            }
    }
    puts("false");
    return 0;
}

30.字符串乘方

给定两个字符串 a 和b，我们定义 a×b 为他们的连接。

例如，如果 a=abc 而 b=def， 则 a×b=abcdef。

如果我们将连接考虑成乘法，一个非负整数的乘方将用一种通常的方式定义：a0=``(空字符串)， $a^{(n+1)}=a×(a^n)$。

输入格式

输入包含多组测试样例，每组测试样例占一行。

每组样例包含一个字符串 s，s 的长度不超过 100。

最后的测试样例后面将是一个点号作为一行。

输出格式

对于每一个 s，你需要输出最大的 n，使得存在一个字符串 a，让 s=an。

输入样例：

abcd
aaaa
ababab
.

输出样例：

1
4
3

思路

这道题的基本思路是：字符串的分割。

• 首先，观察可知，n个重复字符串部分拼接成完整字符串，因此这个n必为完整字符串长度len的一个因子。
• 为了求最大n，必然需要最短的字符串部分，这里将n由大到小遍历
• 再比较划分后的字符串拼接起来是否和完整字符串相等即可。

代码

• 需要注意的点在于string r的定义位置，如果定义为全局变量，由于没有清零机制，会导致r不停累加，最后反而无法匹配了。因此string应定义在循环内。

#include<bits/stdc++.h>
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 r;
                for(int i = 0;i < n;i++)r += str.substr(0,m); 
            if(str == r)
            {
                cout<< n <<endl;
                break;
            }
          }
        }
    }
    return 0;
}