AGC028-A Two Abbreviations

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2");
            WillReturn.Add("acp");
            WillReturn.Add("ae");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3");
            WillReturn.Add("abcdef");
            WillReturn.Add("abc");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15 9");
            WillReturn.Add("dnsusrayukuaiia");
            WillReturn.Add("dujrunuma");
            //45
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        string T = InputList[2];

        long SLen = S.Length;
        long TLen = T.Length;

        long LCM = DeriveLCM2(SLen, TLen);

        List<long> SKouList = DeriveKouList(LCM / SLen, LCM);
        List<long> TKouList = DeriveKouList(LCM / TLen, LCM);

        var SCharDict = new Dictionary<long, char>();
        var TCharDict = new Dictionary<long, char>();
        for (int I = 0; I <= SKouList.Count - 1; I++) {
            SCharDict[SKouList[I]] = S[I];
        }
        for (int I = 0; I <= TKouList.Count - 1; I++) {
            TCharDict[TKouList[I]] = T[I];
        }

        foreach (var EachPair in SCharDict) {
            long CurrKey = EachPair.Key;
            if (TCharDict.ContainsKey(CurrKey) == false) {
                continue;
            }
            if (SCharDict[CurrKey] != TCharDict[CurrKey]) {
                Console.WriteLine(-1);
                return;
            }
        }
        Console.WriteLine(LCM);
    }

    // 公差と上限を引数として数列の項のSetを返す
    static List<long> DeriveKouList(long pKousa, long pJyougen)
    {
        var WillReturn = new List<long>();

        long CurrKou = 1;
        while (true) {
            if (CurrKou > pJyougen) break;
            WillReturn.Add(CurrKou);

            CurrKou += pKousa;
        }
        return WillReturn;
    }

    // 2つの数のLCMを求める
    static long DeriveLCM2(long p1, long p2)
    {
        long GCD = DeriveGCD(p1, p2);
        return (p1 / GCD) * p2;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

解説

考察すると
最小公倍数の長さで、
文字がSとTで一致しなければならない箇所で全て一致するかを
判定すれば良いと分かります。