質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.22%

文字列のパターンを抽出する方法

受付中

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,543

b3638823

score 7

ランダムに生成された文字列からパターンを抽出してグループ化したいのですが、どのようにプログラムを組んだら良いのでしょうか。


あいうえおかきくけこあいうえおかき
あいうえおあいうえお

上記の文字列を例に話します。
「あいうえお」というパターンで4回出てきているのでこれをグループ化。
「あいうえおかき」も2回出てきていますが、「あいうえお」はすでにグループ化されてるので「かき」という部分だけだけをグループ化。

という風にしたいのですが、みなさんはどのようなアルゴリズムを思いつきますか?
全くやり方が思い浮かばないので、非効率な処理になっても構いません。
お知恵をお貸しください。
言語はなんで良いです。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

0

書いているうちにだいぶごちゃごちゃしてしまったので適当に脳内補完してください。

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<string> 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  

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

まず全てのパターンをチェックする所からですね。
その後、何文字以上をやるのか等を決めないと、論理的にルールが策定できません。
アルゴリズムを説明するのは苦手なので、Javascriptでざっくり書いてみました。

var inputText = 'あいうえおかきくけこあいうえおかきあいうえおあいうえお';
var result = {};

for(var start=0; start<inputText.length; start++){
for(var length=(inputText.length - start); length>0; length--){
    var slicedText = inputText.slice(start, length + start);
    if(slicedText == ''){
        break;
    }
    if(result[slicedText] === undefined){
        result[slicedText] = 1;
    } else {
        result[slicedText]++;
    }
}
}
// 結果
console.log(JSON.stringify(result));

結果は以下のように出ます。
この結果から、抽出したいものを取得する様にすれば良いかと思います。
如何でしょうか?
{
    "あ": 4, 
    "あい": 4, 
    "あいう": 4, 
    "あいうえ": 4, 
    "あいうえお": 4, 
    "あいうえおあ": 1, 
    "あいうえおあい": 1, 
    "あいうえおあいう": 1, 
    "あいうえおあいうえ": 1, 
    "あいうえおあいうえお": 1, 
    "あいうえおか": 2, 
    "あいうえおかき": 2, 
    "あいうえおかきあ": 1, 
    "あいうえおかきあい": 1, 
    "あいうえおかきあいう": 1, 
    "あいうえおかきあいうえ": 1, 
    "あいうえおかきあいうえお": 1, 
    "あいうえおかきあいうえおあ": 1, 
    "あいうえおかきあいうえおあい": 1, 
    "あいうえおかきあいうえおあいう": 1, 
    "あいうえおかきあいうえおあいうえ": 1, 
    "あいうえおかきあいうえおあいうえお": 1, 
    "あいうえおかきく": 1, 
    "あいうえおかきくけ": 1, 
    "あいうえおかきくけこ": 1, 
    "あいうえおかきくけこあ": 1, 
    "あいうえおかきくけこあい": 1, 
    "あいうえおかきくけこあいう": 1, 
    "あいうえおかきくけこあいうえ": 1, 
    "あいうえおかきくけこあいうえお": 1, 
    "あいうえおかきくけこあいうえおか": 1, 
    "あいうえおかきくけこあいうえおかき": 1, 
    "あいうえおかきくけこあいうえおかきあ": 1, 
    "あいうえおかきくけこあいうえおかきあい": 1, 
    "あいうえおかきくけこあいうえおかきあいう": 1, 
    "あいうえおかきくけこあいうえおかきあいうえ": 1, 
    "あいうえおかきくけこあいうえおかきあいうえお": 1, 
    "あいうえおかきくけこあいうえおかきあいうえおあ": 1, 
    "あいうえおかきくけこあいうえおかきあいうえおあい": 1, 
    "あいうえおかきくけこあいうえおかきあいうえおあいう": 1, 
    "あいうえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
    "あいうえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
    "い": 4, 
    "いう": 4, 
    "いうえ": 4, 
    "いうえお": 4, 
    "いうえおあ": 1, 
    "いうえおあい": 1, 
    "いうえおあいう": 1, 
    "いうえおあいうえ": 1, 
    "いうえおあいうえお": 1, 
    "いうえおか": 2, 
    "いうえおかき": 2, 
    "いうえおかきあ": 1, 
    "いうえおかきあい": 1, 
    "いうえおかきあいう": 1, 
    "いうえおかきあいうえ": 1, 
    "いうえおかきあいうえお": 1, 
    "いうえおかきあいうえおあ": 1, 
    "いうえおかきあいうえおあい": 1, 
    "いうえおかきあいうえおあいう": 1, 
    "いうえおかきあいうえおあいうえ": 1, 
    "いうえおかきあいうえおあいうえお": 1, 
    "いうえおかきく": 1, 
    "いうえおかきくけ": 1, 
    "いうえおかきくけこ": 1, 
    "いうえおかきくけこあ": 1, 
    "いうえおかきくけこあい": 1, 
    "いうえおかきくけこあいう": 1, 
    "いうえおかきくけこあいうえ": 1, 
    "いうえおかきくけこあいうえお": 1, 
    "いうえおかきくけこあいうえおか": 1, 
    "いうえおかきくけこあいうえおかき": 1, 
    "いうえおかきくけこあいうえおかきあ": 1, 
    "いうえおかきくけこあいうえおかきあい": 1, 
    "いうえおかきくけこあいうえおかきあいう": 1, 
    "いうえおかきくけこあいうえおかきあいうえ": 1, 
    "いうえおかきくけこあいうえおかきあいうえお": 1, 
    "いうえおかきくけこあいうえおかきあいうえおあ": 1, 
    "いうえおかきくけこあいうえおかきあいうえおあい": 1, 
    "いうえおかきくけこあいうえおかきあいうえおあいう": 1, 
    "いうえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
    "いうえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
    "う": 4, 
    "うえ": 4, 
    "うえお": 4, 
    "うえおあ": 1, 
    "うえおあい": 1, 
    "うえおあいう": 1, 
    "うえおあいうえ": 1, 
    "うえおあいうえお": 1, 
    "うえおか": 2, 
    "うえおかき": 2, 
    "うえおかきあ": 1, 
    "うえおかきあい": 1, 
    "うえおかきあいう": 1, 
    "うえおかきあいうえ": 1, 
    "うえおかきあいうえお": 1, 
    "うえおかきあいうえおあ": 1, 
    "うえおかきあいうえおあい": 1, 
    "うえおかきあいうえおあいう": 1, 
    "うえおかきあいうえおあいうえ": 1, 
    "うえおかきあいうえおあいうえお": 1, 
    "うえおかきく": 1, 
    "うえおかきくけ": 1, 
    "うえおかきくけこ": 1, 
    "うえおかきくけこあ": 1, 
    "うえおかきくけこあい": 1, 
    "うえおかきくけこあいう": 1, 
    "うえおかきくけこあいうえ": 1, 
    "うえおかきくけこあいうえお": 1, 
    "うえおかきくけこあいうえおか": 1, 
    "うえおかきくけこあいうえおかき": 1, 
    "うえおかきくけこあいうえおかきあ": 1, 
    "うえおかきくけこあいうえおかきあい": 1, 
    "うえおかきくけこあいうえおかきあいう": 1, 
    "うえおかきくけこあいうえおかきあいうえ": 1, 
    "うえおかきくけこあいうえおかきあいうえお": 1, 
    "うえおかきくけこあいうえおかきあいうえおあ": 1, 
    "うえおかきくけこあいうえおかきあいうえおあい": 1, 
    "うえおかきくけこあいうえおかきあいうえおあいう": 1, 
    "うえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
    "うえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
    "え": 4, 
    "えお": 4, 
    "えおあ": 1, 
    "えおあい": 1, 
    "えおあいう": 1, 
    "えおあいうえ": 1, 
    "えおあいうえお": 1, 
    "えおか": 2, 
    "えおかき": 2, 
    "えおかきあ": 1, 
    "えおかきあい": 1, 
    "えおかきあいう": 1, 
    "えおかきあいうえ": 1, 
    "えおかきあいうえお": 1, 
    "えおかきあいうえおあ": 1, 
    "えおかきあいうえおあい": 1, 
    "えおかきあいうえおあいう": 1, 
    "えおかきあいうえおあいうえ": 1, 
    "えおかきあいうえおあいうえお": 1, 
    "えおかきく": 1, 
    "えおかきくけ": 1, 
    "えおかきくけこ": 1, 
    "えおかきくけこあ": 1, 
    "えおかきくけこあい": 1, 
    "えおかきくけこあいう": 1, 
    "えおかきくけこあいうえ": 1, 
    "えおかきくけこあいうえお": 1, 
    "えおかきくけこあいうえおか": 1, 
    "えおかきくけこあいうえおかき": 1, 
    "えおかきくけこあいうえおかきあ": 1, 
    "えおかきくけこあいうえおかきあい": 1, 
    "えおかきくけこあいうえおかきあいう": 1, 
    "えおかきくけこあいうえおかきあいうえ": 1, 
    "えおかきくけこあいうえおかきあいうえお": 1, 
    "えおかきくけこあいうえおかきあいうえおあ": 1, 
    "えおかきくけこあいうえおかきあいうえおあい": 1, 
    "えおかきくけこあいうえおかきあいうえおあいう": 1, 
    "えおかきくけこあいうえおかきあいうえおあいうえ": 1, 
    "えおかきくけこあいうえおかきあいうえおあいうえお": 1, 
    "お": 4, 
    "おあ": 1, 
    "おあい": 1, 
    "おあいう": 1, 
    "おあいうえ": 1, 
    "おあいうえお": 1, 
    "おか": 2, 
    "おかき": 2, 
    "おかきあ": 1, 
    "おかきあい": 1, 
    "おかきあいう": 1, 
    "おかきあいうえ": 1, 
    "おかきあいうえお": 1, 
    "おかきあいうえおあ": 1, 
    "おかきあいうえおあい": 1, 
    "おかきあいうえおあいう": 1, 
    "おかきあいうえおあいうえ": 1, 
    "おかきあいうえおあいうえお": 1, 
    "おかきく": 1, 
    "おかきくけ": 1, 
    "おかきくけこ": 1, 
    "おかきくけこあ": 1, 
    "おかきくけこあい": 1, 
    "おかきくけこあいう": 1, 
    "おかきくけこあいうえ": 1, 
    "おかきくけこあいうえお": 1, 
    "おかきくけこあいうえおか": 1, 
    "おかきくけこあいうえおかき": 1, 
    "おかきくけこあいうえおかきあ": 1, 
    "おかきくけこあいうえおかきあい": 1, 
    "おかきくけこあいうえおかきあいう": 1, 
    "おかきくけこあいうえおかきあいうえ": 1, 
    "おかきくけこあいうえおかきあいうえお": 1, 
    "おかきくけこあいうえおかきあいうえおあ": 1, 
    "おかきくけこあいうえおかきあいうえおあい": 1, 
    "おかきくけこあいうえおかきあいうえおあいう": 1, 
    "おかきくけこあいうえおかきあいうえおあいうえ": 1, 
    "おかきくけこあいうえおかきあいうえおあいうえお": 1, 
    "か": 2, 
    "かき": 2, 
    "かきあ": 1, 
    "かきあい": 1, 
    "かきあいう": 1, 
    "かきあいうえ": 1, 
    "かきあいうえお": 1, 
    "かきあいうえおあ": 1, 
    "かきあいうえおあい": 1, 
    "かきあいうえおあいう": 1, 
    "かきあいうえおあいうえ": 1, 
    "かきあいうえおあいうえお": 1, 
    "かきく": 1, 
    "かきくけ": 1, 
    "かきくけこ": 1, 
    "かきくけこあ": 1, 
    "かきくけこあい": 1, 
    "かきくけこあいう": 1, 
    "かきくけこあいうえ": 1, 
    "かきくけこあいうえお": 1, 
    "かきくけこあいうえおか": 1, 
    "かきくけこあいうえおかき": 1, 
    "かきくけこあいうえおかきあ": 1, 
    "かきくけこあいうえおかきあい": 1, 
    "かきくけこあいうえおかきあいう": 1, 
    "かきくけこあいうえおかきあいうえ": 1, 
    "かきくけこあいうえおかきあいうえお": 1, 
    "かきくけこあいうえおかきあいうえおあ": 1, 
    "かきくけこあいうえおかきあいうえおあい": 1, 
    "かきくけこあいうえおかきあいうえおあいう": 1, 
    "かきくけこあいうえおかきあいうえおあいうえ": 1, 
    "かきくけこあいうえおかきあいうえおあいうえお": 1, 
    "き": 2, 
    "きあ": 1, 
    "きあい": 1, 
    "きあいう": 1, 
    "きあいうえ": 1, 
    "きあいうえお": 1, 
    "きあいうえおあ": 1, 
    "きあいうえおあい": 1, 
    "きあいうえおあいう": 1, 
    "きあいうえおあいうえ": 1, 
    "きあいうえおあいうえお": 1, 
    "きく": 1, 
    "きくけ": 1, 
    "きくけこ": 1, 
    "きくけこあ": 1, 
    "きくけこあい": 1, 
    "きくけこあいう": 1, 
    "きくけこあいうえ": 1, 
    "きくけこあいうえお": 1, 
    "きくけこあいうえおか": 1, 
    "きくけこあいうえおかき": 1, 
    "きくけこあいうえおかきあ": 1, 
    "きくけこあいうえおかきあい": 1, 
    "きくけこあいうえおかきあいう": 1, 
    "きくけこあいうえおかきあいうえ": 1, 
    "きくけこあいうえおかきあいうえお": 1, 
    "きくけこあいうえおかきあいうえおあ": 1, 
    "きくけこあいうえおかきあいうえおあい": 1, 
    "きくけこあいうえおかきあいうえおあいう": 1, 
    "きくけこあいうえおかきあいうえおあいうえ": 1, 
    "きくけこあいうえおかきあいうえおあいうえお": 1, 
    "く": 1, 
    "くけ": 1, 
    "くけこ": 1, 
    "くけこあ": 1, 
    "くけこあい": 1, 
    "くけこあいう": 1, 
    "くけこあいうえ": 1, 
    "くけこあいうえお": 1, 
    "くけこあいうえおか": 1, 
    "くけこあいうえおかき": 1, 
    "くけこあいうえおかきあ": 1, 
    "くけこあいうえおかきあい": 1, 
    "くけこあいうえおかきあいう": 1, 
    "くけこあいうえおかきあいうえ": 1, 
    "くけこあいうえおかきあいうえお": 1, 
    "くけこあいうえおかきあいうえおあ": 1, 
    "くけこあいうえおかきあいうえおあい": 1, 
    "くけこあいうえおかきあいうえおあいう": 1, 
    "くけこあいうえおかきあいうえおあいうえ": 1, 
    "くけこあいうえおかきあいうえおあいうえお": 1, 
    "け": 1, 
    "けこ": 1, 
    "けこあ": 1, 
    "けこあい": 1, 
    "けこあいう": 1, 
    "けこあいうえ": 1, 
    "けこあいうえお": 1, 
    "けこあいうえおか": 1, 
    "けこあいうえおかき": 1, 
    "けこあいうえおかきあ": 1, 
    "けこあいうえおかきあい": 1, 
    "けこあいうえおかきあいう": 1, 
    "けこあいうえおかきあいうえ": 1, 
    "けこあいうえおかきあいうえお": 1, 
    "けこあいうえおかきあいうえおあ": 1, 
    "けこあいうえおかきあいうえおあい": 1, 
    "けこあいうえおかきあいうえおあいう": 1, 
    "けこあいうえおかきあいうえおあいうえ": 1, 
    "けこあいうえおかきあいうえおあいうえお": 1, 
    "こ": 1, 
    "こあ": 1, 
    "こあい": 1, 
    "こあいう": 1, 
    "こあいうえ": 1, 
    "こあいうえお": 1, 
    "こあいうえおか": 1, 
    "こあいうえおかき": 1, 
    "こあいうえおかきあ": 1, 
    "こあいうえおかきあい": 1, 
    "こあいうえおかきあいう": 1, 
    "こあいうえおかきあいうえ": 1, 
    "こあいうえおかきあいうえお": 1, 
    "こあいうえおかきあいうえおあ": 1, 
    "こあいうえおかきあいうえおあい": 1, 
    "こあいうえおかきあいうえおあいう": 1, 
    "こあいうえおかきあいうえおあいうえ": 1, 
    "こあいうえおかきあいうえおあいうえお": 1
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.22%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る