Codeforces 798 B. Mike and strings-String的find()函数

好久好久好久之前的一个题，今天翻cf，发现这个题没过，补一下。

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

input

2
molzv
lzvmo

output

input

3
kc
kc
kc

output

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".

题意：给定的n个串，最少能移动几次使得这n个字符串相等。每次只能将字符串首位的移动到末尾。

想法：以某个串为标准，改变其他的字符串，找出变化次数最小的。

这个题用string中的find()函数，简直不要太炫酷。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100+10;
 4 string a[N];
 5 
 6 int main(){
 7     int n,i,j;
 8     while(~scanf("%d",&n)){
 9         for(i=0;i<n;i++)
10             cin>>a[i];
11         int ans=0x3f3f3f,flag=0;
12         for(i=0;i<n;i++){
13             int sum=0;
14             for(j=0;j<n;j++){
15                 string tmp=a[j]+a[j];
16                 if(tmp.find(a[i])==string::npos)flag=1;
17                 else sum+=tmp.find(a[i]);
18             }
19             ans=min(ans,sum);
20         }
21         printf("%d
",flag?-1:ans);
22     }
23     return 0;
24 }

string中的find()函数，查找字符串A是否包含子串B,不是用strA.find(strB) > 0而是strA.find(strB) != string:npos

返回的值是B在A中第一次出现的下标位置，如果没有查询到，则返回string::npos，如果返回npos就输出-1。

关于string中的find函数，看其他人写的吧。

传送门:1.哇哇哇2.呜呜呜3.汪汪汪4.喂喂喂

Codeforces 798 B. Mike and strings-String的find()函数

相关推荐