uva455

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc").

Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.

Sample Input

HoHoHo

Sample Output

题目类型：简单字符处理

算法分析：周期变量zhouqi从1开始枚举到字符串的长度len，其中舍去判断不能被len整除的zhouqi。对于可能为最小周期的zhouqi使用求余的方法进行判断。注意本题最后一组数据的输出之后是没有空行的，下面第一个代码是更好的实现

/**************************************************
filename       :j.cpp
author         :maksyuki
created time   :2017/12/2 10:02:00
last modified  :2017/12/2 10:19:40
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t, id = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        
        int len = strlen(s);
        int minval = len;
        for(int i = 1; i < len; i++) {
            if(len % i) continue;
            strncpy(v, s, i);
            v[i] = 0;
            strcpy(tmp, v);
            bool is_find = true;
            char *p = NULL;
            int len2 = len / i;
            for(int j = 1; j <= len2; j++) {
                p = strstr(s, tmp);
                strcat(tmp, v);
                if(p == NULL) {
                    is_find = false;
                    break;
                }
            }
            if(is_find) {
                minval = i;
                break;
            }
        }
        if(id++ > 1) puts("");
        printf("%d\n", minval);
    }
    return 0;
}

100

101

102

/**************************************************

filename :j.cpp

author :maksyuki

created time :2017/12/2 10:02:00

last modified :2017/12/2 10:19:40

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t, id = 1;

scanf("%d", &t);

while(t--) {

scanf("%s", s);

int len = strlen(s);

int minval = len;

for(int i = 1; i < len; i++) {

if(len % i) continue;

strncpy(v, s, i);

v[i] = 0;

strcpy(tmp, v);

bool is_find = true;

char *p = NULL;

int len2 = len / i;

for(int j = 1; j <= len2; j++) {

p = strstr(s, tmp);

strcat(tmp, v);

if(p == NULL) {

is_find = false;

break;

}

if(is_find) {

minval = i;

break;

}

if(id++ > 1) puts("");

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

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn = 86;

char a[maxn];

int main()
{
    int cases;
    //ifstream cin ("aaa.txt");

    cin >> cases;
    while (cases--)
	{
        cin >> a;
        int len = strlen (a);

        int zhouqi, i;
        bool isend = false;

        for (zhouqi = 1; !isend; zhouqi++)
		{
            if (len % zhouqi == 0)
			{
                 for (i = 0; a[i]; i++)
				 {
                    if (a[i] != a[(i+zhouqi)%len])
						break;
				 }
			}

            if (i == len)
                isend = true;
		}

			if (cases)
                printf ("%d\n\n", --zhouqi);

            else
                printf ("%d\n", --zhouqi);

	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 86;

char a[maxn];

int main()

{

int cases;

//ifstream cin ("aaa.txt");

cin >> cases;

while (cases--)

{

cin >> a;

int len = strlen (a);

int zhouqi, i;

bool isend = false;

for (zhouqi = 1; !isend; zhouqi++)

{

if (len % zhouqi == 0)

{

for (i = 0; a[i]; i++)

{

if (a[i] != a[(i+zhouqi)%len])

break;

}

if (i == len)

isend = true;

}

if (cases)

printf ("%d\n\n", --zhouqi);

else

printf ("%d\n", --zhouqi);

}

return 0;

}

uva401

uva678

一	二	三	四	五	六	日
« 6月
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

超客的水墨烟雨

uva455

分类目录

标签云

书签

近期评论