今回は paiza の「決まり字」の問題に挑戦！
とうとう、決まり字の本題を解いていく！
問題概要
- 百人一首のように、複数の和歌の上の句が与えられる。
- その中の
m番目の和歌 の「決まり字（＝一意に特定できる最短の先頭部分）」を求める。
🔍 決まり字とは？
- 他のどの和歌とも接頭部分が被らない位置までの文字列。
- つまり、
- 最長共通接頭辞（LCP）が最も長い相手との一致部分 + 1文字目 まで。
- それで一意に特定できる。
入力例:
9 3 // n m
kirigirisunakuyashimoyonosamushironi
kimigatameharunononiidetewakanatsumu
chihayaburukamiyomokikazutatsutagawa
ookotonotaeteshinakuwanakanakani
ooeyamaikunonomichinotokereba
ookenakuukiyonotaminioukana
chigiriokishisasemogatsuyuoinochinite
kimigatameoshikarazarishiinochisae
chigirikinakataminisodeoshiboritsusu
出力例:
chih
✅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);
const a = s[m-1]; // 決まり字を求めたい和歌
let count = 0; // 最大の共通接頭辞の長さ
for (let i = 0; i < n; i++) {
if (i === m-1) continue; // 自分とは比較しない
const b = s[i]; // 比較相手の和歌
let tempCount = 0; // このペアでの共通接頭辞長
for (let j = 0; j < Math.min(a.length, b.length); j++) {
if (a[j] === b[j]){
tempCount++;
} else {
break; // 違ったら比較終了
}
}
// 最も長く一致した相手の長さを保持
if (tempCount > count) count = tempCount;
}
// 決まり字は共通部分＋1文字
const ans = a.slice(0, count + 1);
console.log(ans);
});
-
入力を受け取る（
n, m, 各和歌の上の句） -
m番目の和歌（調べたい和歌）をaに保存。 -
全ての他の和歌と 1つずつ比較。
-
各比較で「最長共通接頭辞の長さ（LCP）」を数える。
-
その中で 最大のLCP長 を求める。
-
aの先頭から「最大LCP長 + 1」文字目までを切り出す。
→ それが「決まり字」。
📝まとめ
-
最長共通接頭辞（LCP） の考え方を全ての組み合わせに応用。
-
一番似ている相手 を見つける → その共通部分＋1文字が「決まり字」。
-
slice(0, count + 1)の「+1」が重要（共通部分だけでは区別できないため）。 -
Math.min(a.length, b.length)で短い方の長さまで比較。 -
breakを使って無駄なループを避ける。 -
比較対象を
if (i === m-1) continue;でスキップするのもポイント。