CF-798B

B. Mike and strings

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Mike has?n?strings?s1,?s2,?...,?sn?each consisting of lowercase English letters. In one move he can choose a string?si, erase the first character and append it to the end of the string. For example, if he has the string "coolmike", in one move he can transform it into the string "oolmikec".

Now Mike asks himself: what is minimal number of moves that he needs to do in order to make all the strings equal?

Input

The first line contains integer?n?(1?≤?n?≤?50) — the number of strings.

This is followed by?n?lines which contain a string each. The?i-th line corresponding to string?si. Lengths of strings are equal. Lengths of each string is positive and don't exceed?50.

Output

Print the minimal number of moves Mike needs in order to make all the strings equal or print??-?1?if there is no solution.
Examples
input
4
xzzwo
zwoxz
zzwox
xzzwo
output
5
input
2
molzv
lzvmo
output
2
input
3
kc
kc
kc
output
0
input
3
aa
aa
ab
output
-1
Note

In the first sample testcase the optimal scenario is to perform operations in such a way as to transform all strings into "zwoxz".

?

題意：

將所有字符串變成相等，只允許將最左邊的字符移到最右，問最少要移多少步。

若不能使所有相等，則輸出-1、

分別以每一個字符串為模板，將其他的字符串移成和當前字符串相等的情況，再找出步數最少的方案。

附AC代碼：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int inf=1<<30;
 5 
 6 string s[60];
 7 
 8 int main(){
 9     int n,i,j,k,m;
10     cin>>n;
11     for(i=0;i<n;i++){
12         cin>>s[i];
13     }
14     int len=s[0].size();
15     int ans=inf;
16     for(i=0;i<n;i++){
17         int cnt=0;
18         for(j=0;j<n;j++){
19             for(m=0;m<len;m++){
20                 for(k=0;k<len;k++){
21                     if(s[i][k]!=s[j][(k+m)%len])
22                     break;
23                 }
24                 if(k==len)//只有len個都相等才表明移動m個字符后兩字符串相等 
25                 break;
26             }
27             if(m==len){//若m==len則表明不能匹配。 
28                 cnt=inf;
29                 break;
30             }
31             cnt+=m;
32         }
33         ans=min(ans,cnt);
34     }
35     if(ans==inf)
36     cout<<-1<<endl;
37     else
38     cout<<ans<<endl;
39     return 0;
40 }

轉載于:https://www.cnblogs.com/Kiven5197/p/6770323.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/252802.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/252802.shtml
英文地址，請注明出處：http://en.pswp.cn/news/252802.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！