UVa 455 Periodic Strings

解題策略

這題要找出字串中的最小週期，我的作法比較好玩一些。
首先用兩個指針i,j分別指向字串的頭兩個字母，像這樣：

abcdabcd
↑↑

我的基本想法很簡單，讓i,j之間保持一個固定間距，如果這個間距就是週期，那麼且同步往後移動指針，比對字母，i,j指的兩字母應該要一直都相同。

# 例子:不管何時，兩指針的字母皆同。
abcabcabc
↑  ↑
abcabcabc
 ↑  ↑
abcabcabc
  ↑  ↑

那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字，不同表示尚未找到週期，拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j]，這時候可能就是字串中的週期出現了，同步移動指針 (++i,++j) 持續往後比對。

這個作法有兩個Special case要考慮

1. 字串只有一個字母的時候(長度為1)，兩根指針還能指去哪，直接return 1。
2. 有時候字串尾巴會出現一些破壞週期的字母，例如：abcabcabcd，或者hohaho。所以最後必須檢查找到的週期，跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了，週期值直接等於字串長度。

	/**
	* UVa 455 Periodic Strings
	* Author: chchwy
	* Last Modified: 2010.04.22
	*/
	#include<iostream>
	int findPeriod(char* buf)
	{
	int len = strlen(buf);
	if (len == 1) return 1; //special case
	int i = 0, j = 1;
	while (buf[j] != NULL) //reach the end of string
	{
	if (buf[i] == buf[j])
	++i, ++j;
	else
	++j;
	}
	return ( len % (j - i) == 0 ) ? j - i : len;
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("455.in", "r", stdin);
	#endif
	int caseNum;
	scanf("%d ", &caseNum);
	while ( caseNum-- )
	{
	char buf[256];
	scanf("%s", buf);
	printf("%d\n", findPeriod(buf) );
	if ( caseNum > 0 ) putchar('\n');
	}
	return 0;
	}

view raw 455.cpp hosted with ❤ by GitHub