#UVa:455-Periodic Strings

灆洢 2016-04-20 03:12:06

從週期1開始往後迭代找尋週期長度為字串長度之因數者是否為該字串之週期即可得解。

C++(0.000)

/*******************************************************/
/* UVa 455 Periodic Strings                            */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

bool isPeriod(const string &periodString, int period){
  for( int i = 0 ; i < period ; ++i ){
    for( int j = i+period ; j < periodString.length() ; j += period ){
      if( periodString[i] != periodString[j] ){
        return false;
      }
    }
  }

  return true;
}

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    string periodString;
    for( int caseNumber = 0 ; caseNumber < N ; ++caseNumber ){
      if( caseNumber > 0 ){
        printf("\n");
      }
      cin >> periodString;

      for( int period = 1 ; period <= periodString.length() ; ++period ){
        if( periodString.length() % period == 0 && isPeriod(periodString, period) ){
          printf("%d\n", period);
          break;
        }
      }
    }
  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料