算法笔记 15_循环单词



问题描述:


如果一个单词通过循环右移获得的单词,我们称这些单词都为一种循环单词。 例如:picture 和 turepic 就是属于同一种循环单词。 现在给出n个单词,需要统计这个n个单词中有多少种循环单词。 


链接:https://www.nowcoder.com/questionTerminal/9d5fbe7750a34d0b91c73943f93b2d7d
来源:牛客网




输入描述:
输入包括n+1行:
第一行为单词个数n(1 ≤ n ≤ 50)
接下来的n行,每行一个单词word[i],长度length(1 ≤ length ≤ 50)。由小写字母构成
输出描述:
输出循环单词的种数


示例1

输入

5
picture
turepic
icturep
word
ordw

输出

2



解题思路:

把要测试的单词后再重复下这个单词,如:picture ,变成 picturepicture

然后判断其他要测试的单词是不是这个串的子串(长度要先相等)

但是有特殊情况:比如sandsand,and是子串,但是和sand不是同一种循环单词

因此算法首先要判断不同串的长度是否相同


C++ 实现:

#include"stdafx.h"
#include <string>
#include <iostream>
#include <vector>
using namespace std;


int main()
{
	int n, num = 0;
	vector<string> twords;	// 声明一个字符串容器,名儿叫twords
	vector<bool> checks;	// 定义一个bool容器,判断是否已属于某种循环单词
	cin >> n;	// 输入要输入几个单词
	for (int i = 0; i < n; i++)
	{
		string t_w;
		cin >> t_w;
		twords.push_back(t_w); // 将用户输入的数据插到数组后面
		checks.push_back(false); // 默认全部不匹配
	}

	for (int j = 0; j < n; j++)
	{
		if (!checks[j]) {
			string tt;
			tt = twords[j] + twords[j]; // 重复数组并拼接

			for (int k = j + 1; k < n; k++) 
			{
				if (!checks[k]) {
					if (tt.find(twords[k]) !=
						string::npos&&twords[k].length() == twords[j].length()) { // npos默认值-1,.find()函数若找不到对象则返回-1
						checks[k] = true;
					}
				}
			}
			num++;
		}
	}
	cout << "一共有: " << num << "个单词。" << endl;

	system("pause");
	return 0;
}


happysneaker.comhappysneaker.com

运行结果

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论