循环单词

问题描述

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

输入描述

输入包括n+1行：
第一行为单词个数n(1 ≤ n ≤ 50)
接下来的n行，每行一个单词word[i]，长度length(1 ≤ length ≤ 50)。由小写字母构成

输出描述

输出循环单词的种数

输入例子

5
picture
turepic
icturep
word
ordw

输出例子

2

分析

考虑到需要大量查找操作，使用unordered_set作为容器。
遍历整个容器，把当前单词的所有循环单词都枚举出来（单词最大长度为50，是可以枚举的），然后检测这些循环单词在容器中存不存在。最后把容器中存在的循环单词和当前单词都删除掉，计数器加1。接着进入下一个循环，一样的操作。

note

看评论里有人说可以把每个单词都变成自己和自己的串接，然后判断其他单词是不是自己的子串就知道其是否是自己的循环单词了。比如单词是picture，串接后的单词就是picturepicture，turepic和icturep都是picturepicture的子串，因此都是picture的循环单词。

代码

1.unordered_set版

#include <cstdio>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

string leftShiftOne(const string &str)
{
    string shiftedStr = str;
    shiftedStr.front() = str.back();
    for (int i = 1; i < str.size(); i++)
        shiftedStr[i] = str[i - 1];

    return shiftedStr;
}

int main()
{
    int n;
    scanf("%d", &n);

    unordered_set<string> us;
    for (int i = 0; i < n; i++)
    {
        char str[51];
        scanf("%s", str);
        us.insert(str);
    }

    int cnt = 0;
    for (auto iter = us.begin(); iter != us.end(); )
    {
        string shiftedStr = *iter;
    
        for (int i = 0; i < shiftedStr.size() - 1; i++)
        {
            shiftedStr = leftShiftOne(shiftedStr);
            if (shiftedStr != *iter && us.find(shiftedStr) != us.end())
            {
                us.erase(shiftedStr);
            }
        }
        iter = us.erase(iter);

        cnt++;
    }

    printf("%d\n", cnt);

    return 0;
}

2.串接单词版

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    list<string> words;
    for (int i = 0; i < n; i++)
    {
        string word;
        cin >> word;
        words.push_back(word);
    }

    int cnt = 0;
    for (auto outerIter = words.begin(); outerIter != words.end(); )
    {
        string catStr = *outerIter + *outerIter;
        for (auto innerIter = words.begin(); innerIter != words.end(); )
        {
            if (innerIter != outerIter && 
                outerIter->size() == innerIter->size() * 2 &&
                catStr.find(*innerIter) != string::npos)
                innerIter = words.erase(innerIter);
            else
                innerIter++;
        }

        outerIter = words.erase(outerIter);
        cnt++;
    }

    printf("%d\n", cnt);

    return 0;
}