超时了有没有快一点的算法???

//代码
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
//#include<list>
using namespace std;
bool isrotate(string& s1, string& s2)
{
if (s1.size() != s2.size()) return false;
for (auto it = s2.begin(); it != s2.end(); it++)
{
string str1(s2.begin(), it);
string str2(it, s2.end());
if (s1 == (str1 + str2) || s1 == (str2 + str1))return true;
}
return false;
}
int main()
{
//测试代码
vector<string> words = { "abba", "abab", "baba", "abab", "baba", "bbaa", "aabb" };
//list<string> word(words.begin(),words.end());
//我用list报错,所以勉强用vector 做删除,但是vector 删除会让迭代器失效,所以我选择置空
vector<string> word;
auto it = words.begin();
while (it != words.end())
{
auto it2 = it;
it2++;
while (it2 != words.end())
{
if ( *it2!="" && isrotate(*it, *it2) ) {
//words.erase(it2++);
*it2 = "";
// continue;
}
it2++;
}
word.push_back(*it);
it++;
while ( it!=words.end() && *it == "")
it++;
}
cout << word.size() << endl;
return 0;
}

题目翻译:旋转单词,如果两个单词是旋转单词那么他们属于同一旋转单词类,
求不同的旋转单词类的数量,
旋转单词: 不好描述就像例子那样

顶

最后一个测试数据至少5000个

顶一顶

再顶顶

我发的版本是先判断是否为循环单词，如果是就置空(删除，考虑到vector删除费时所以置空)然后所有遍历都跳过空字符，让words中每种单词只有一个，然后压入word中求其数量

我在C++吧发的版本是，如果为循环单词则覆盖为前一个单词，交换到前一个被比较单词附近然后去重，(后来改为计数)

终于是搞好了

//通过代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
inline bool isrotate( const string& s1,const string& s2)
{
if (s1.size() != s2.size())return false;
int size = s1.size();
int i = 0;
int m = 0;
for (; m != size; m++)
{
if (s1[i] == s2[m]) i++;
else if (i != 0 && s1[i] != s2[m]) i = 0,m--;
}
if (i != 0)
{
m = 0;
for (; i != size; i++)
if (s1[i] == s2[m]) m++;
else break;
}
if (i == size) return true;
return false;
}
inline bool compare(const string& s1,const string& s2)
{
return s1.size() < s2.size();
}
int main()
{
//测试代码
vector<string> words = { "abba", "bbaa", "baab", "aabb", "abba" };
//list<string> words(word.begin(), word.end());不能用list
stable_sort(words.begin(), words.end(),compare);//oj的时候去掉这个
int i = 0;
for (auto it = words.begin(); it != words.end(); it++)
{
for (auto it2 = it + 1; it2 != words.end(); it2++)
{
if (it->size() != it2->size()) break;
if (isrotate(*it, *it2)) swap(*(++it),*it2);
}
i++;
}
cout << i << endl;
//return i;
return 0;
}

核心的函数就是isrotate
这个函数就写的很丑,不过全部是字符的比较,免去了大量重复的比较,所以还是很快的