UVa 455 : Periodic Strings

恩恩，我今天突然發現我已經好久好久沒有使用 Blogger 了 = =
大概有一年了吧
所以我就來寫一下吧~反正現在放暑假了嘛~~ (攤

---

今天要講的是 UVa 455 : Periodic Strings
原文網址 :
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=396
(注意 : 不要用 Google Chrome 開喔!)

反正這題主要講的是給你 N 個字串，問你這 N 個字串的最小週期是多少，那週期是什麼呢?
假設今天字串A能夠被分成 k 個部分，而且這 k 個部分都是一樣的，那麼我們可以說這個字串A有週期 k
例如 : "abababab" 著個字串有週期 2 ( "ab" ) 、 週期 4 ( "abab" ) 和週期 8 ( "abababab ")

解題想法 :

首先，要讓週期 k 成立的條件一定是 k 要是字串的字元個數的因數，否則就無法分成 k 等分了，因此，我先用一個迴圈查看 k 是否為因數

接著，再看看這個 k 等分是否都一樣，在下面的程式碼可以看到 : 我利用 Check( ) 函數來確認週期 k 是否成立 ( 我的程式碼是以 n 來實作 )，我是將這個字串後面的 k-1 份去查看是不是和第一份完全相同，如果相同就回傳 true ( 其實我以前都直接回傳 1 的，不過最近有再接觸 python ，所以又變成了 return true 了   XDD)

那麼，對於比對的方式，我是利用 index 的方式實作，首先第一個變數 i 是控制目前比對的組數，第一組應該是 0 ，不過因為不用和自己比，所以就從 1 開始，那麼裡面的 j 就是控制第 i 組的第 j 個字啦!!

首先，第一組的 index 一定是 0 ~ k-1 嘛，那第二組就是 ( 0 + i*k ) ~ ( k-1 + i*k ) ，所以我再作比對的時候我只要比對 index 是 j 的值和 index 是 j % k 的值是否一樣就大功告成啦!!!

還有，最後的輸出格式也要注意啊!!!我在那裏吃了 3 個 WA 啊~~ ( 跪

然後我還要小小道個歉，我一開始沒注意到是週期 k ，所以我的函數參數是 n ，這裡可能會造成一些小混亂，我會改進的! QAQ

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

bool Check(string ans,int n)
{
    for (int i=1;i<ans.length()/n;i++)
    {
        for (int j=i*n;j<(i+1)*n;j++)
            if (ans[j] != ans[(j)%n])
                return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        string input;
        cin >> input;
        for (int i=1;i<=input.length();i++)
        {
            if ( !(input.length()%i) && Check(input,i))
            {
                cout << i << endl;
                break;
            }
        }
        if ( n > 0 )
            cout << endl;
    }
    return 0;
}

---

後記 : 

我覺得我光是打這篇就打得好辛苦喔 QQ
我找了好多嵌入程式碼的方法都失敗了，最後只好開大絕，直接把程式碼貼上來了，超詭異的啦! ( 更新!!! 我成功啦~~~ 不過好像不能讓人複製貼上ㄟ )
看來我還要多多摸索 Blogger 使用方法才行啊~~