文字列操作のアルゴリズムが思いつかないので知恵をお貸しください

Question

どのように正解を導き出せば良いのかアルゴリズムがわかりません。

たとえば、標準入力で次の値が与えられるとします。

入力例1
5
ABCDE
DEABC

let N = Int(readLine()!)!
let S1 = readLine()!
let S2 = readLine()!

このように、標準入力をまずは受け取ります。

Nは文字数、S1は揃えたい文字、S2は揃える前の文字です。

そして、S2を左に何回ずらせばS1と同じになるのかを出したいです。

上記の標準入力の場合は、２回です。

入力例2
3
ABC
CAB

出力
1

どうかよろしくお願いいたします。

Comments

[m.ts10806]

>わりません

細かいですがこういう誤字はノイズとなって要件を伝える際の邪魔になりえます。
文章はしっかり書きましょう。

[siorukuru]

修正しました。

Answer 1

左にN回ずらすという操作は
ABCから左N文字取り、残りの文字列の末尾にくっつける操作
になるのかなと思います。

でしたら、

1. n = 0
2. S1の先頭1文字がS2の先頭からd文字目にあることを確認する (d>=nの整数)
3. S2をd文字分左に操作した文字列S2′をS1と比較し合致しない場合はn=dとして2へ
   合致したら、dを出力し終了

みたいな感じですかね

Comments

[siorukuru]

参考になりました。ありがとうございます。

Answer 2

知恵ということでコードは示しません。考え方だけ。

1. 繰り返し回数をゼロに
2. S1 と S2 を比較 --> 一致していたら終わり
3. 繰り返し回数が N 回に達していたら終わり
4. 一致しなければ一番左側の文字をS2の文字列から削除 - A
5. 削除した文字を A の文字列の一番右側につけた文字列を作成し S2 へセット
6. 繰り返し回数をカウントアップ
7. 2番目〜ここまでの処理を繰り返す

Comments

[ironya]

ベタすぎですな。。。反省

[siorukuru]

とても参考になりました。ありがとうございます。

Answer 3

一番ラクそうなのは、「一致するまで左にずらして、そのずらした回数をカウントアップする」、でしょうね。

---

追記１：
Swiftの文字列操作は面倒くさいので、左に１回ずらす関数のサンプルを作ってみました。

extension String {
    func rotateLeft() -> String {
        return String(suffix(count - 1) + prefix(1))
    }
}

let S2 = "CAB"
print(S2) // "CAB"
print(S2.rotateLeft()) // "ABC" ※結果は戻り値という点に注意

あとは躓くポイントは無さそうです。

---

追記２：
使う必要があるかは判りませんが、ずらしていった結果、一致するかという判定は以下のページの手法使えば簡単にできそうですね。

https://medium.com/@notestomyself/string-rotation-in-swift-ab5b38721c56

---

追記３：
あれ、もしかして"CABCAB"から"ABC"のオフセットを探すだけで答えになるんじゃ？

---

追記４：
追記３のコードをPlaygroundで書いてみました。
一応動いているようには見えます。

import Foundation

let S1 = "ABCDE" // 期待値
let S2 = "DEABC" // ずらす前

let S2S2 = String(S2 + S2)
if let range = S2S2.range(of: S1) {
    print(S2S2.distance(from: S2S2.startIndex, to: range.lowerBound)) //2
} else {
    print("error")
}

Comments

[ironya]

追記2のリンク先の方法良いですね。
追記3は追記2そのものですね。

[takabosoft]

追記２は判定しているだけで、回転回数は出していないので、そこは出さないといけないです。

[siorukuru]

うまくいきました。とても参考になる解答ありがとうございます！

[takabosoft]

????
私も頭の体操になりました。

[ironya]

> 回転回数は出していないので、そこは出さないといけないです。
仰せのとおりです。