1

文字列内のテキストを見つけて置き換える方法を知っている人はいますか? 基本的に私は2つの文字列を持っています:

string firstS = "/9j/4AAQSkZJRgABAQEAYABgAAD/2wBDABQODxIPDRQSERIXFhQYHzMhHxwcHz8tLyUzSkFOTUlBSEZSXHZkUldvWEZIZoxob3p9hIWET2ORm4+AmnaBhH//2wBDARYXFx8bHzwhITx/VEhUf39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f3//";

string secondS = "abcdefg2wBDABQODxIPDRQSERIXFh/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/abcdefg";

firstS含まれている一連の文字が含まれているかどうかを検索してsecondS、それを置き換えたいと思います。また、角括弧内の置き換えられた文字の数に置き換える必要があります。

[置換文字数]

たとえば、firstS両方secondSに「2wBDABQODxIPDRQSERIXFh」と「/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/f39/」が含まれているため、これらを置き換える必要があります。 . したがって、次のようにfirstSなります。

string firstS = "/9j/4AAQSkZJRgABAQEAYABgAAD/[22]QYHzMhHxwcHz8tLyUzSkFOTUlBSEZSXHZkUldvWEZIZoxob3p9hIWET2ORm4+AmnaBhH//2wBDARYXFx8bHzwhITx/VEhUf39[61]f3//";

それが理にかなっていることを願っています。正規表現でこれを行うことができると思いますが、その非効率性は好きではありません。誰かが別のより速い方法を知っていますか?

4

4 に答える 4

3

誰かが別のより速い方法を知っていますか?

はい、この問題には実際に適切な名前があります。これは最長共通部分文字列と呼ばれ、かなり高速なソリューションを備えています。

これはideone の実装です。10 文字以上の一般的な部分文字列をすべて検索して置き換えます。

// This comes straight from Wikipedia article linked above:
private static string FindLcs(string s, string t) {
    var L = new int[s.Length, t.Length];
    var z = 0;
    var ret = new StringBuilder();
    for (var i = 0 ; i != s.Length ; i++) {
        for (var j = 0 ; j != t.Length ; j++) {
            if (s[i] == t[j]) {
                if (i == 0 || j == 0) {
                    L[i,j] = 1;
                } else {
                    L[i,j] = L[i-1,j-1] + 1;
                }
                if (L[i,j] > z) {
                    z = L[i,j];
                    ret = new StringBuilder();
                }
                if (L[i,j] == z) {
                    ret.Append(s.Substring( i-z+1, z));
                }
            } else {
                L[i,j]=0;
            }
        }
    }
    return ret.ToString();
}
// With the LCS in hand, building the answer is easy
public static string CutLcs(string s, string t) {
    for (;;) {
        var lcs = FindLcs(s, t);
        if (lcs.Length < 10) break;
        s = s.Replace(lcs, string.Format("[{0}]", lcs.Length));
    }
    return s;
}
于 2012-08-29T00:51:44.577 に答える
1

「最長共通部分文字列」と「最長共通部分列」の間には十分注意する必要があります。

サブストリングの場合: http://en.wikipedia.org/wiki/Longest_common_substring_problem

サブシーケンスの場合: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

これら 2 つのトピックについて、YouTube でいくつかのビデオもご覧になることをお勧めします http://www.youtube.com/results?search_query=longest+common+substring&oq=longest+common+substring&gs_l=youtube.3..0.3834.10362.0. 10546.28.17.2.9.9.2.225.1425.11j3j3.17.0...0.0...1ac.lSrzx8rr1kQ

http://www.youtube.com/results?search_query=longest+common+subsequence&oq=longest+common+s&gs_l=youtube.3.0.0l6.2968.7905.0.9132.20.14.2.4.4.0.224.2038.5j2j7.14.0... 0.0...1ac.4CYZ1x50zpc

ここで、最長共通部分列の C# 実装を見つけることができます。

http://www.alexandre-gomes.com/?p=177

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence

于 2012-08-29T01:22:45.490 に答える
0

同様の問題がありますが、単語の出現についてです! だから、これが役立つことを願っています。私が使用SortedDictionaryした二分探索木

/* Application counts the number of occurrences of each word in a string
   and stores them in a generic sorted dictionary. */
using System;
using System.Text.RegularExpressions;
using System.Collections.Generic;

public class SortedDictionaryTest
{
   public static void Main( string[] args )
   {
      // create sorted dictionary
      SortedDictionary< string, int > dictionary = CollectWords();

      // display sorted dictionary content
      DisplayDictionary( dictionary );
   } 

   // create sorted dictionary 
   private static SortedDictionary< string, int > CollectWords()
   {
      // create a new sorted dictionary
      SortedDictionary< string, int > dictionary =
         new SortedDictionary< string, int >();

      Console.WriteLine( "Enter a string: " ); // prompt for user input
      string input = Console.ReadLine(); 

      // split input text into tokens
      string[] words = Regex.Split( input, @"\s+" );

      // processing input words
      foreach ( var word in words )
      {
         string wordKey = word.ToLower(); // get word in lowercase

         // if the dictionary contains the word
         if ( dictionary.ContainsKey( wordKey ) )
         {
            ++dictionary[ wordKey ];
         } 
         else
            // add new word with a count of 1 to the dictionary
            dictionary.Add( wordKey, 1 );
      } 

      return dictionary;
   } 

   // display dictionary content
   private static void DisplayDictionary< K, V >(
      SortedDictionary< K, V > dictionary )
   {
      Console.WriteLine( "\nSorted dictionary contains:\n{0,-12}{1,-12}",
         "Key:", "Value:" );

      /* generate output for each key in the sorted dictionary
        by iterating through the Keys property with a foreach statement*/
      foreach ( K key in dictionary.Keys )
         Console.WriteLine( "{0,- 12}{1,-12}", key, dictionary[ key ] );

      Console.WriteLine( "\nsize: {0}", dictionary.Count );
   } 
}
于 2012-08-29T01:28:56.063 に答える
0

これはおそらく非常に遅いですが、技術的負債を負うことを厭わず、プロトタイピングのために今すぐ何かが必要な場合は、LINQ を使用できます。

string firstS = "123abc";
string secondS = "456cdeabc123";
int minLength = 3;

var result = 
    from subStrCount in Enumerable.Range(0, firstS.Length)
    where firstS.Length - subStrCount >= 3
    let subStr = firstS.Substring(subStrCount, 3)
    where secondS.Contains(subStr)
    select secondS.Replace(subStr, "[" + subStr.Length + "]");

結果は

 456cdeabc[3] 
 456cde[3]123
于 2012-08-29T03:36:26.690 に答える