今回は paiza の「「決まり字」を解くために : part4」の問題に挑戦！
問題概要
-
2 つの和歌の上の句が与えられるので、和歌
mの決まり字を求める。 -
決まり字とは：
→ ある和歌を一意に特定できる「最小限の先頭部分の文字列」。 -
求め方の考え方：
- まず2つの和歌の**最長共通接頭辞（LCP）**を見つける。
例：akiが共通なら LCP の長さは 3。 - 決まり字は、その共通部分の「次の1文字まで」。
→ つまり、akiの次の文字を足したakinが和歌1の決まり字になる。
入力例:
2 1 // n m
akinotanokarihonoionotomaoarami
akikazenitanabikukumonotaemayori
出力例:
akin
✅OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, m] = lines[0].split(' ').map(Number);
const s = lines.slice(1);
for (let i = 0; i < Math.min(s[0].length, s[1].length); i++) {
if (s[0][i] !== s[1][i]) {
const ans = s[m-1].slice(0, i+1);
console.log(ans);
break;
}
}
});
-
2つの和歌を1文字ずつ比較
→forループで、短い方の文字数（Math.min）までチェックする。 -
初めて違う文字が出た位置を発見したら
→ その位置iまでが「共通部分（最長共通接頭辞）」
→slice(0, i+1)で「その次の1文字まで」を切り出す。 -
決まり字を出力して処理終了
→console.log(ans)で、和歌mの「決まり字」を出力。
→breakでループを抜ける（以降の比較は不要）。
✅OK例２：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, m] = lines[0].split(' ').map(Number);
const s = lines.slice(1);
// 最長共通接頭辞の長さを求める
let lcp = 0;
for (let i = 0; i < Math.min(s[0].length, s[1].length); i++) {
if (s[0][i] === s[1][i]) {
lcp++;
} else {
break;
}
}
// 決まり字 = 共通部分の次の文字まで
const result = s[m - 1].slice(0, lcp + 1);
console.log(result);
});
📝 まとめ
🔹 最長共通接頭辞 (LCP) = 先頭から何文字一致するかを数える。
🔹 決まり字 = LCP + 次の1文字。
🔹 文字列比較はインデックス i で1文字ずつ行う。
🔹 slice(0, i+1) で「先頭からi+1文字」を簡単に取得できる。