コンテンツにスキップ

文字列

タグ「文字列」の記事 10 件

SamCoding Round 10 (Div. 4) D - Bead Necklace

英小文字からなる文字列 ss が与えられます。ss が ppp…pppp\ldots p(pp を何度も繰り返した文字列)の先頭部分になるような、最も短い文字列 pp を求める問題です(∣s∣≤106|s| \le 10^6)。

∣s∣=n|s| = n とします。長さ ii の pp は ss の先頭 ii 文字に決まり、条件は「すべての j≥ij \ge i で sj=sj−is_j = s_{j-i}」、つまり ss の ii 文字目以降(0 始まり)が ss の先頭部分になっていることです。

これは Z algorithm で調べられます。Z algorithm は、各 ii について ss と ss の ii 文字目以降の最長共通接頭辞の長さ ziz_i を O(n)O(n) で求めます。条件は zi=n−iz_i = n - i と同じなので、これを満たす最小の i≥1i \ge 1 を探し、先頭 ii 文字を出力します。そのような ii がなければ、ss 全体が答えです。

計算量は O(n)O(n) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/string.hpp"
void solve() {
STR(S);
auto z = z_algorithm(S);
rep(i, 1, len(S)) {
if (z[i] == len(S) - i) {
print(S.substr(0, i));
return;
}
}
print(S);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

z_algorithm は上の ziz_i を求める関数です。

使用ライブラリ:cpp_include@cb82602

競プロキャンプ2026関西 J - Substring Query

英小文字からなる文字列 SS が与えられます。QQ 個のクエリで文字列 TiT_i が与えられるので、SS と TiT_i の両方の部分文字列である空でない文字列のうち、最長のものの長さを答える問題です(なければ 00)。制約は 1≤∣S∣≤20001 \le |S| \le 2000、1≤Q≤2×1051 \le Q \le 2 \times 10^5、∑∣Ti∣≤106\sum |T_i| \le 10^6 です。

TT の各位置 jj について、TT の jj 文字目で終わる文字列のうち SS の部分文字列であるものの最長の長さを ℓj\ell_j とします。共通の部分文字列はどれも TT のどこかの位置で終わるので、答えは ℓj\ell_j の最大値です。

ℓj\ell_j は、SS の Suffix Automaton を使うと、TT を前から 1 文字ずつ読みながら求められます。Suffix Automaton は SS のすべての部分文字列を受理するオートマトンです。各状態は SS の部分文字列の集まりを表し、状態の数は O(∣S∣)O(|S|) です。

TT の jj 文字目までを読んだとき、長さ ℓj\ell_j の文字列(その位置で終わる、SS の部分文字列である最長の文字列)を表す状態 vv と ℓj\ell_j を持っておきます。次の文字 cc を読むときは、次のようにします。

  • vv から cc で遷移できれば、遷移して長さを 11 増やす。
  • 遷移できなければ、先頭の文字を削って短くする。Suffix Automaton では、これは suffix link をたどることにあたる。遷移できるようになるか初期状態に戻るまでたどってから、遷移を試す。

長さは 1 文字読むごとに高々 11 しか増えないので、suffix link をたどる回数の合計は ∣T∣|T| 以下です。よって、1 つのクエリは O(∣T∣)O(|T|) で処理でき、全体の計算量は O(∣S∣+∑∣Ti∣)O(|S| + \sum |T_i|) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/suffix-automaton.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(Q);
STR(S);
SuffixAutomaton sam(S);
rep(Q) {
STR(T);
print(max(sam.match_lengths(T)));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SuffixAutomaton は Suffix Automaton で、既定では英小文字を扱います。match_lengths(T) は上の ℓj\ell_j を TT の各位置について並べた列を返すので、その最大値を出力しています。

使用ライブラリ:cpp_include@c3d3c0f

DOJ Beginner Contest 11 D - Cipher Guess

英大文字だけからなる NN 個の暗号文の単語 C1,C2,…,CNC_1, C_2, \dots, C_N と、平文の単語 SS が与えられます。

単一換字式暗号(同じ文字は同じ文字に、異なる文字は異なる文字に置き換える)で SS を変換した結果になりうる単語を、候補とよびます。候補のうち暗号文に最も多く現れる単語を求める問題です。同数なら辞書順で最小のものを答え、候補がなければ -1 を出力します。

∣Ci∣,∣S∣≤20|C_i|, |S| \le 20 で、NN の総和は 10510^5 以下です。

単語 CC が候補であるための条件は、「SS で同じ文字が現れる位置の組」と「CC で同じ文字が現れる位置の組」が一致することです。

たとえば ABBA なら、A の位置が {0,3}\{0, 3\}、B の位置が {1,2}\{1, 2\} です。XYYX も {0,3},{1,2}\{0, 3\}, \{1, 2\} に分かれるので候補です。XYYY は {0},{1,2,3}\{0\}, \{1, 2, 3\} になるので候補ではありません。

そこで、各単語について文字ごとの出現位置のリストを作り、それをソートしたものを比べます。長さが違う単語は、位置の範囲が違うので自然に一致しません。

候補を Counter で数えます。あらかじめ CC を辞書順にソートしておくと、Counter には辞書順に単語が入ります。most_common は同数の要素を入れた順に返すので、most_common(1) で「最多で、同数なら辞書順最小」の単語が得られます。

単語の長さを LL とすると、全体で O(NL+Nlog⁡N)O(NL + N \log N) です。

Python
from collections import defaultdict, Counter
for _ in range(int(input())):
N = int(input())
C = input().split()
C.sort()
S = input()
d = defaultdict(list)
for i, a in enumerate(S):
d[a].append(i)
ans = Counter()
X = sorted(d.values())
for f in C:
d = defaultdict(list)
for i, a in enumerate(f):
d[a].append(i)
Y = sorted(d.values())
if X == Y:
ans[f] += 1
if ans:
print(ans.most_common(1)[0][0])
else:
print(-1)

DOJ Beginner Contest 6 A - Dadas-style Acronyms

英字と空白からなる文 SS が与えられます。SS を空白で単語に分け、各単語の最初の文字を順につなげた略語を出力する問題です。大文字と小文字は変えません。

単語の間には空白がちょうど 1 つあり、文の最初と最後には空白がありません。

SS を空白で区切り、各単語の先頭の文字を取り出してつなげます。

Python では input().split() で単語のリストが得られるので、各単語の x[0] を "".join でつなげれば答えになります。

Python
for _ in range(int(input())):
print("".join(map(lambda x: x[0], input().split())))

DOJ Beginner Contest 9 A - AI slop

英小文字からなる長さ NN の文字列 SS が与えられます。SS が ai を部分文字列(連続する部分)として含めば AI slop、含まなければ Human made と出力する問題です。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 5×1055 \times 10^5 以下です。

SS に ai が含まれるかを調べるだけです。

a と i がどちらも含まれていても、a のすぐ後ろに i が来ていなければ条件を満たしません(たとえば artificialintelligence は Human made です)。隣り合う 2 文字が a、i の順になっている場所を探します。

Python では "ai" in S で、ai が部分文字列として含まれるかを判定できます。

Python
for _ in range(int(input())):
N = int(input())
S = input()
if "ai" in S:
print("AI slop")
else:
print("Human made")

ShareOJ - Blank

半角スペースだけからなる文字列 SS が与えられるので、その長さを出力する問題です。1≤∣S∣≤1001 \le |S| \le 100 です。

入力の 1 行をそのまま読み、長さを数えます。

注意が要るのは読み込み方です。スペースを区切りとして読み飛ばす方法では、SS を読めません。たとえば C++ の cin >> S は空白を読み飛ばすので、SS は空になってしまいます。C++ なら getline(cin, S) のように、行全体を読む必要があります。

Python の input() は行末の改行だけを取り除き、スペースはそのまま残します。そのため、len(input()) で答えが求まります。逆に input().split() や input().strip() を使うと、スペースが消えてしまいます。

Python
print(len(input()))

yukicoder contest 517 A - Happy End

英大文字からなる長さ NN の文字列 SS があります(5≤N≤3×1055 \le N \le 3 \times 10^5)。文字列 TT が「良い」とは、TT の末尾 5 文字が HAPPY で、それ以外の場所に HAPPY が部分文字列として現れないことをいいます。

SS の 1 文字を別の文字に書き換える操作を繰り返して SS を良い文字列にするとき、操作回数の最小値を求めてください。

末尾 5 文字は必ず HAPPY にしなければならないので、HAPPY と異なる文字の個数だけ書き換えが必要です。

次に、末尾以外に現れる HAPPY をすべて壊します。ここで大事なのは、HAPPY 同士は重なって現れないことです。HAPPY の中で H は先頭にしかないので、HAPPY の途中から別の HAPPY が始まることはありません。

そのため、末尾以外に現れる HAPPY は、末尾の HAPPY とも互いにも重なりません。重ならない HAPPY を 1 つ壊すには少なくとも 1 文字書き換える必要があり、1 回の書き換えで 2 つ同時に壊すこともできません。よって、末尾以外に現れる HAPPY の個数が、この段階で必要な操作回数の下限になります。

この下限は達成できます。各 HAPPY の 1 文字を、HAPPY に含まれない文字(たとえば Z)に書き換えればよいです。HAPPY に含まれない文字を含む位置からは新しい HAPPY が生まれないので、書き換えによって別の場所に HAPPY ができることはありません。

答えは 2 つの段階の操作回数の和で、計算量は O(N)O(N) です。

Python
N = int(input())
S = list(input())
ans = 0
for i in range(1, 6):
if S[-i] != "HAPPY"[-i]:
S[-i] = "HAPPY"[-i]
ans += 1
for i in range(N - 5):
if S[i : i + 5] == list("HAPPY"):
S[i + 4] = "Z"
ans += 1
print(ans)

前半のループで末尾 5 文字を HAPPY にそろえ、後半のループで末尾以外の HAPPY を見つけるたびに最後の Y を Z に書き換えています。

牛客小白月赛138 B - Is it Palidrome?

英小文字と ? からなる長さ nn の文字列 ss があります。それぞれの ? を好きな英小文字に置き換えます。

  • どう置き換えても回文になるなら certainly
  • どう置き換えても回文にならないなら impossible
  • 回文になる置き換え方とならない置き換え方の両方があるなら possible

を出力してください(nn の総和 ≤5×105\le 5 \times 10^5)。

回文かどうかは、左右対称な位置にある文字のペア (si,sn−1−i)(s_i, s_{n-1-i})(0≤i<⌊n/2⌋0 \le i < \lfloor n/2 \rfloor)がすべて等しいかどうかで決まります。そこで、ペアを次の 3 種類に分けます。

  • どちらも英小文字で、異なる:どう置き換えてもこのペアは等しくならないので、回文にはなりません。
  • 少なくとも一方が ?:? の置き換え方しだいで、等しくすることも異なるものにすることもできます。
  • どちらも英小文字で、等しい:どう置き換えてもこのペアは等しいままです。

ペアごとの ? の置き換えは互いに独立に選べるので、答えは次のようになります。

  1. 異なる英小文字のペアが 1 つでもあれば impossible
  2. そうでなく、? を含むペアが 1 つでもあれば possible(すべてのペアを等しくすることも、そのペアだけを異なるものにすることもできる)
  3. どちらでもなければ certainly

nn が奇数のときの真ん中の文字はどのペアにも入らないので、? であっても回文かどうかに影響しません。3 つ目のサンプル xy?yx が certainly になるのはこのためです。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
p = False
ng = False
for i in range(N//2):
if S[i] == "?":
p = True
continue
if S[N-i-1] == "?":
p = True
continue
if S[i] != S[N-i-1]:
ng = True
continue
if ng:
print("impossible")
elif p:
print("possible")
else:
print("certainly")

p は ? を含むペアがあるか、ng は異なる英小文字のペアがあるかを表します。ループを N//2 までにしているので、真ん中の文字は自然に見ないことになります。

ABC477 C - Range Search Query

文字列 S,TS, T が与えられます。QQ 個のクエリ (L,R)(L, R) それぞれについて、SS の LL 文字目から RR 文字目までの部分に TT が含まれるかを判定する問題です(∣S∣≤4×105|S| \le 4 \times 10^5、∣T∣≤10|T| \le 10、Q≤2×105Q \le 2 \times 10^5)。

SS の LL 文字目から RR 文字目までに TT が含まれるのは、TT が SS の ii 文字目から始まって出現するような ii が L≤i≤R−∣T∣+1L \le i \le R - |T| + 1 の範囲にあるときです。

そこで、前処理として SS の各位置から TT が始まるかを調べておきます。∣T∣≤10|T| \le 10 なので、各位置で愚直に比べても O(∣S∣∣T∣)O(|S||T|) で間に合います。これの累積和をとっておけば、各クエリでは区間 [L,R−∣T∣+1][L, R - |T| + 1] にある開始位置の個数が O(1)O(1) で求まり、それが 11 以上なら Yes です。

Python
Q = int(input())
S = input()
T = input()
N, M = len(S), len(T)
acc = [0] * (N + 1)
for i in range(N):
acc[i + 1] = acc[i] + S.startswith(T, i)
for _ in range(Q):
L, R = map(int, input().split())
print("Yes" if L - 1 <= R - M and acc[R - M + 1] > acc[L - 1] else "No")

acc[i] は、TT の出現のうち開始位置(0 始まり)が ii 未満のものの個数です。0 始まりで開始位置が L−1L - 1 以上 R−∣T∣R - |T| 以下の出現があるかを、acc[R - M + 1] > acc[L - 1] で調べています。R−L+1<∣T∣R - L + 1 < |T| のときは区間が空なので、先に L - 1 <= R - M で除いています。

Uiua
⋅◌⍥◡(&p⨬"No""Yes">0/-⬚0⊏-:⊜⋕⊸≠@ &sc):⊙:[2⧻]⟜(\+⌕)&sc&sc⋕&sc

⋕&sc で QQ、続く 2 つの &sc で SS と TT を読みます。

⟜(\+⌕) では、⌕ で SS の各位置から TT が始まるかの 0/1 の列を作り、\+ で累積和 PP にします。PkP_k は開始位置(0 始まり)が kk 以下の出現の個数です。⟜ で TT を残しておき、[2⧻] で [2,∣T∣][2, |T|] を作ります。:⊙: で並べ替えて、QQ の下に [2,∣T∣][2, |T|] と PP が来るようにしています。

⍥◡(…) で、[2,∣T∣][2, |T|] と PP を残したまま中の処理を QQ 回繰り返します。中の処理は次のとおりです。

  1. ⊜⋕⊸≠@ &sc でクエリを読んで [L,R][L, R] にします。
  2. -: で [L,R]−[2,∣T∣]=[L−2,R−∣T∣][L, R] - [2, |T|] = [L - 2, R - |T|] を計算します。
  3. ⬚0⊏ で PP からこの 2 か所を取り出し、/- で PR−∣T∣−PL−2P_{R - |T|} - P_{L - 2} を求めます。これが区間内にある開始位置の個数です。L=1L = 1 のときの添字 −1-1 は、⬚0 で 00 として扱っています。
  4. >0 で 11 個以上あるかを判定し、⨬"No""Yes" で文字列を選んで &p で出力します。

最後の ⋅◌ で、残しておいた [2,∣T∣][2, |T|] と PP を捨てています。

ABC477 A - Traffic Light

信号機の色は B(青)→ Y(黄)→ R(赤)→ B → … の順に周期的に変わります。現在の色 cc が与えられるので、次の色を出力する問題です。

"BYR" の中で cc が何番目かを調べ、同じ位置にある「次の色」を "YRB" から取り出せば答えになります。

現在の色BYR
次の色YRB
Python
print("YRB"["BYR".index(input())])
Uiua
&p⊏⊗&sc"BYR""YRB"

"YRB" と "BYR" を積み、&sc で cc を読みます。⊗ で "BYR" の中での cc の位置を求め、⊏ でその位置の文字を "YRB" から取り出して &p で出力しています。Python 版と同じ処理です。

なお、AtCoder の Uiua は最新版と ⊗(index of)の引数の順序が逆です。最新版では ⊗ の 2 つの引数が入れ替わるので、このコードはそのままでは動きません。