题意:已知n个字符串,问经过多少次操作可以使得所有字符串相等。 每次操作: 对于当前字符串,把s[0]放到s的最后一个
思路:首先明确一点,次数最少,我们必须得以某一个字符串s为原型,其他去尽可能靠近s(合理)。以每一个字符串s为基础,对于其他字符串,因为头会到尾部,那么我们把字符串t*2(首尾相连)。 用string find函数在字符串*2中去寻找s,如果没找到那么会返回string::npos。 如果找到了,会返回该字符串的前一个下标。比如s=’a’ t=’baa’ 那么t.find(s)=1 正好就是把前面放到后面的次数。
数据分析:1 ≤ n ≤ 50
复杂度分析:O(n^2)
学习了:string s1,s2; s1.find(s2) 在中寻找s2,如果找到了返回前一个下标,否则返回string :: npos。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s[60];
int main(void)
{
int n;
cin >>n ;
for(int i=1;i<=n;i++)
cin >> s[i];
int ans=INT_MAX;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
{
string temp=s[j]+s[j];
if(temp.find(s[i])==string::npos)
{
printf("-1\n");
return 0;
}
else
cnt+=temp.find(s[i]);
}
ans=min(ans,cnt);
}
cout << ans <<endl;
}