質問編集履歴
2
コンパクトにしました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,8 +1,4 @@
|
|
|
1
|
-
演習 サフィックスアレイ（Suffix Array）
|
|
2
|
-
|
|
3
|
-
|
|
1
|
+
文字列の操作，ソート，二分探索．
|
|
4
|
-
|
|
5
|
-
予想コーディング量：120行程度．
|
|
6
2
|
|
|
7
3
|
ドキュメント中に，ある文字列が含まれているかを探すプログラムを作成したいです。
|
|
8
4
|
|
|
@@ -24,20 +20,6 @@
|
|
|
24
20
|
|
|
25
21
|
という文字列になる．（これをすべての単語について行う．）
|
|
26
22
|
|
|
27
|
-
2. 上記の文字列をソートする．
|
|
28
|
-
|
|
29
|
-
3. 探したい文字列を入力し，それを上記のソートされた文字列の並びから二分探索で探す．（普通は，いろいろな文字列を探すので，このステップ3は無限ループとなる．）
|
|
30
|
-
|
|
31
|
-
検索対象ファイルは，”tom.txt”とする．ステップ1の前に，ファイルから単語を読み込む必要がある．今回は空白は単語区切りと考え，例えば”a b”のような文字列を探すことは考えなくて良い．従って，scanfの書式%sで読み込めば良い．
|
|
32
|
-
|
|
33
|
-
ステップ1で，本当にサフィックスの文字列を作り出すなどという無駄なことはしないように注意．既に存在する文字列の途中をポインタで指すようにする．
|
|
34
|
-
|
|
35
|
-
ステップ2では，ポインタの配列をソートする．
|
|
36
|
-
|
|
37
|
-
ステップ3では，ポインタの配列の中から目的の文字列を探す．二分探索のプログラムを使う．この時，文字列全体が一致しなくても良いことに注意する．例えば，“uff”を探している場合は，”uffix”のように先頭から3文字が一致していれば，”uff”はファイルに含まれていたということになる（ヒント: strncmpという関数がある）．uffを含む単語は複数あることに注意．そのすべてサフィックスを表示すること．オリジナルの単語は表示しなくてよい．サフィックスだけ表示すればよい．
|
|
38
23
|
|
|
39
24
|
|
|
40
|
-
|
|
41
|
-
|
|
25
|
+
この動きをする関数がわかりません。
|
|
42
|
-
|
|
43
|
-
tom.txtというテキストは自分がもっています。
|
1
アドバンスコースを削除しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
|
|
5
5
|
予想コーディング量：120行程度．
|
|
6
6
|
|
|
7
|
-
ドキュメント中に，ある文字列が含まれているかを探すプログラムを作成
|
|
7
|
+
ドキュメント中に，ある文字列が含まれているかを探すプログラムを作成したいです。
|
|
8
8
|
|
|
9
9
|
|
|
10
10
|
|
|
@@ -36,6 +36,8 @@
|
|
|
36
36
|
|
|
37
37
|
ステップ3では，ポインタの配列の中から目的の文字列を探す．二分探索のプログラムを使う．この時，文字列全体が一致しなくても良いことに注意する．例えば，“uff”を探している場合は，”uffix”のように先頭から3文字が一致していれば，”uff”はファイルに含まれていたということになる（ヒント: strncmpという関数がある）．uffを含む単語は複数あることに注意．そのすべてサフィックスを表示すること．オリジナルの単語は表示しなくてよい．サフィックスだけ表示すればよい．
|
|
38
38
|
|
|
39
|
-
【拡張へのヒント: オリジナルの単語を表示する．また，ファイルの先頭から何行目にその文字列が出現したのかも表示できるようにする．もちろん，出現したすべての行数を表示する．】
|
|
40
39
|
|
|
40
|
+
|
|
41
|
+
まず、ステップ１を行う関数がわかりません。
|
|
42
|
+
|
|
41
|
-
|
|
43
|
+
tom.txtというテキストは自分がもっています。
|