アルゴリズムと
データ構造
第12回
文字列処理
C言語の文字列
文字列とは
プログラム上で文字の並びを表す
中身が空でもよい
文字列リテラル
文字の並びを2つの引用符で囲んだもの
各文字は記憶域上で連続して配置
終端にはナル文字が自動的に付加
内容は基本的に書き換え不可
C言語の文字列
文字列リテラル
文字列リテラル“STRING”
01010011
文字’S’ (0x53)
S T R I N G \0
01010100
文字’T’ (0x54)
01010010
文字’R’ (0x52)
01001001
文字’I’ (0x49)
01001110
文字’N’ (0x5E)
01000111
文字’G’ (0x47)
00000000
ナル文字’\0’ (0)
C言語の文字列
文字列リテラルの特徴
型と値
char *型・評価値は先頭文字へのポインタ
記憶域期間
静的記憶域期間：プログラム開始から終了まで記憶域を占有
同一つづりの文字列リテラル
格納領域が同一か別かは処理系依存
定数性
文字列リテラルの記憶域への値の書き込みは定義なし：どうなる
かは処理系依存・やるべきではない
C言語の文字列
配列による文字列
文字列をchar型配列に格納することで、値の読
み書きが可能
終端にはナル文字が必要
ナル文字がないとプログラム暴走の恐れ
ナル文字以降どのような内容があろうと無視
配列
S T R I N G \0
文字列
無視
C言語の文字列
文字列の初期化
配列宣言の際に初期化可能
代入式では初期化式無効
char st[10] = {‘S’, ‘T’, ‘R’, ‘I’, ‘N’, ‘G’, ‘\0’};
char st[10] = “STRING”;
/* 上の式と同等 */
char st[10];
st = {‘S’, ‘T’, ‘R’, ‘I’, ‘N’, ‘G’, ‘\0’};
st = “STRING”;
/* エラー */
/* エラー */
C言語の文字列
ポインタによる文字列
文字列リテラルを指し示すのにポインタを使用
各文字へのアクセスは配列へのアクセスと同様
pt
char *pt = “1234”;
ポインタ
1 2 3 4 \0
文字列リテラル
・仮に文字列リテラルが1000番地から格納されていれば、ptには1000が入る
文字列の基本操作
文字列の長さ
配列要素数と文字列長は必ずしも一致しない
配列全体を使い切っているとは限らない
文字列先頭からナル文字を線形探索
最初に見つかったナル文字までが文字列
ナル文字のある要素の添え字が文字列の長さ
ナル文字はカウントしない
必ずナル文字が存在：探索失敗を考慮する必要なし
ある意味番兵法ともいえる
文字列の基本操作
文字列の長さ
int str_len(const char *s) {
int len = 0;
while (s[len])
len++;
return (len);
}
文字列の基本操作
文字列の長さ
int str_len(const char *s) {
int len = 0;
while (*s++)
len++;
return (len);
}
文字列の基本操作
文字列の長さ
int str_len(const char *s) {
char *p = s;
while (*s)
s++;
return (s - p);
}
文字列の基本操作
文字列からの文字の探索
文字列先頭から対象文字を線形探索
最初に見つかった位置が求める位置
見つかる前にナル文字がきたら探索失敗
文字列の基本操作
文字列からの文字の探索
int str_chr(const char *s, int c) {
int i;
for (i = 0; s[i] != c; i++)
if (s[i] == ‘\0’)
return (-1);
return (i);
}
文字列の基本操作
文字列からの文字の探索
char *str_chr(const char *s, int c) {
for ( ; *s != c; s++)
if (*s == ‘\0’)
return (NULL);
return ((char *) s);
}
文字列の基本操作
文字列の比較
2つの文字列を先頭から順に比較
すべての文字が等しかったら等しいと判断
途中で違う文字列がきたら大小比較
違う部分の文字のそれぞれの文字コードの大小で比較
文字コードの体系により比較結果に差異
文字列の基本操作
文字列の比較
int str_cmp(const char *s1, const char *s2) {
while (*s1 == *s2) {
if (*s1 == ‘\0’)
return (0);
s1++; s2++;
}
return ((unsigned char) *s1 - (unsigned char) *s2));
}
文字列探索
文字列探索とは
文字列中に、別の文字列が存在するかを探索
探し出す文字列：パターン
探索される文字列：テキスト
文字列探索
力まかせ法
単純法・素朴法
テキストの先頭から順次パターンと比較
一致するまで、パターン位置を1文字ずつずらし
て再比較
最後まで一致しなかったら含まれない
文字列探索
力まかせ法
A
B
A
B
A
B
C
\0
C
D
\0
E
F
G
H
A
\0
文字列探索
力まかせ法
pt
A
B
A
B
A
B
C
\0
pp
C
D
\0
E
F
G
H
A
\0
文字列探索
KMP法
Knuth-Morris-Pratt法
不一致文字に出会ったときのそれまでの照合結
果を有効利用
テキスト中とパターン中の重なり部分を見つけ、
パターンの移動を大きく
テキスト走査位置が前進のみ
文字列探索
KMP法
Z
A
B
C
A
B
X
A
B
C
B
C
A
A
B
D
B
\0
D
A
C
C
A
D
E
F
\0
文字列探索
KMP法における照合再開位置
A
B
C
A
B
D
\0
A
B
C
A
B
D
\0
A
B
C
A
B
D
0
0
0
1
2
0
文字列探索
KMP法
pt
Z
A
B
C
A
B
X
A
C
C
A
B
C
B
C
A
A
B
D
B
\0
D
A
B
C
A
B
D
0
0
0
1
2
0
pp
A
D
E
F
\0
文字列探索
Boyer-Moore法
BM法
照合をパターン末尾から実行
一致しない文字がきたとき、その文字に応じてパ
ターンの移動量を決定
文字列探索
Boyer-Moore法
A
B
C
X
D
A
B
A
C
\0
E
Z
C
A
B
A
A
C
A
B
A
C
\0
文字列探索
Boyer-Moore法におけるスキップテーブル
パターンと一致しなくなった文字ごとに、照合中の
文字を何文字分ずらすかの移動量を計算
パターン文字長がnの場合
パターンに含まれない文字の移動量：n
パターンに含まれる文字の移動量:n - k - 1
k：最後に出現する位置の添え字
パターン末尾の文字はノーカウント
文字列探索
Boyer-Moore法におけるスキップテーブル
0
1
2
3
A
B
A
C
A
1
B
2
C
4
D
4
E
4
F
4
G
4
H
4
I
4
J
4
K
4
L
4
M
4
N
4
O
4
P
4
Q
4
R
4
S
4
T
4
U
4
V
4
W
4
X
4
Y
4
Z
4
文字列探索
Boyer-Moore法
pt
A
B
C
X
D
A
B
A
C
\0
E
Z
C
A
B
pp
A
1
B
2
AB以外
4
A
C
A
B
A
C
\0
© Copyright 2024 ExpyDoc
