質問: ランダムに生成された文字列からパターンを抽出してグループ化したいのですが、どのようにプログラムを組んだら良いのでしょうか。 ``` あいうえおかきくけこあいうえおかき あいうえおあいうえお ``` 上記の文字列を例に話します。 「あいうえお」というパターンで4回出てきているのでこれをグループ化。 「あいうえおかき」も2回出てきていますが、「あいうえお」はすでにグループ化されてるので「かき」という部分だけだけをグループ化。 という風にしたいのですが、みなさんはどのようなアルゴリズムを思いつきますか? 全くやり方が思い浮かばないので、非効率な処理になっても構いません。 お知恵をお貸しください。 言語はなんで良いです。
回答: 書いているうちにだいぶごちゃごちゃしてしまったので適当に脳内補完してください。 1. 先頭の字を検索文字列に読み込む 2. 検索文字が自身以外に対象文字列中に存在することを確認 3-1. 存在する場合 3-1-2. 対象文字列中の次の文字を検索文字列の末尾に追記し、自身以外に対象文字列中に存在することを確認 3-1-3. 対象文字列中に検索文字列が存在しなくなるまで3-1-1.を繰り返す 3-1-4. 対象文字列中に検索文字列が存在しなくなったら、最後の一文字を読み込む前の検索文字列をグループとする 3-1-5. グループとした文字列を対象文字列中から削除し、1.に戻る 3-2. 存在しない場合 3-2-1. 次の文字を読み込み、2. に戻る ``` あいうえおかきくけこあいうえおかき あいうえおあいうえお ``` 上記の文字列に当てはめると 1. 「あ」を読み込み、対象文字列に「あ」が存在することを確認する。 2. 「あい」を読み込み、対象文字列に「あい」が存在することを確認する。 3. 上記を繰り返し、「あいうえお」を読み込み、対象文字列に「あいうえお」が存在することを確認する。 4. 「あいうえおか」を読み込み、対象文字列に「あいうえおか」が存在しないことを確認する。 5. 4.にて「あいうえおか」が存在しないため、「あいうえお」をグループとし、文字列から「あいうえお」を削除する。 6. この時点で対象文字列は「かきくけこかき」 7. 「か」を読み込み、対象文字列に「か」が存在することを確認する。 8. 「かき」を読み込み、対象文字列に「かき」が存在することを確認する。 9. 上記を繰り返し、「かきく」を読み込み、対象文字列に「かき」が存在することを確認する。 10. 9.にて「かきく」が存在しないため、「かき」をグループとし、文字列から「かき」を削除する。 11. この時点で対象文字列は「くけこ」 12. 「く」を読み込み、対象文字列に「く」が存在しないことを確認する。 13. 「け」を読み込み、対象文字列に「け」が存在しないことを確認する。 14. 「こ」を読み込み、対象文字列に「こ」が存在しないことを確認する。 追記 上の間違ってました。すいません。「あいうえおかき」でグループになってしまいますね。 utunさんの言うとおりもう少しルールがないと絞り込めませんね。 utunさんを参考にc#で ``` using System; using System.Collections.Generic; using System.Linq; namespace TestTeraTail { class Program { static void Main() { var inputText = "あいうえおかきくけこあいうえおかきあいうえおあいうえお"; var result = ExtractGroup(inputText); foreach (var group in result) { Console.WriteLine("Group:" + group + " Count:" + SearchCount(inputText, group)); } Console.ReadLine(); } private static IEnumerable ExtractGroup(string source) { while (source.Length > 1) { var result = Enumerable.Range(0, source.Length) .Select(i => new { StartIndex = i , LengthRange = Enumerable.Range(1, source.Length - i) }) .SelectMany(x => x.LengthRange.Select(i => source.Substring(x.StartIndex, i))) .Select(x => new { Group = x, Count = SearchCount(source, x) }) .Where(x => x.Count > 1) .OrderByDescending(x => x.Group.Length) .OrderByDescending(x => x.Count) .FirstOrDefault(); if (result == null) yield break; yield return result.Group; source = source.Replace(result.Group, ""); } } private static int SearchCount(string source, string x) { return (source.Length - source.Replace(x, "").Length) / x.Length; } } } ``` 実行結果 ``` Group:あいうえお Count:4 Group:かき Count:2 ```