[c#] C #에서 더 큰 문자열에서 하위 문자열의 모든 위치 찾기

Program / 글쓴이

구문 분석해야하는 큰 문자열이 있고의 모든 인스턴스를 찾아서 extract"(me,i-have lots. of]punctuation각각의 인덱스를 목록에 저장해야합니다.

따라서이 문자열 조각이 더 큰 문자열의 시작과 중간에 있다고 가정하면 둘 다 발견되고 해당 인덱스가 List. 그리고 그것은 무엇이든 List포함 0하고 다른 색인을 포함 합니다.

나는 주위 놀았 던, 그리고는 string.IndexOf않습니다 거의 내가 찾고, 나는 몇 가지 코드를 작성했습니다 무엇을 – 그러나 그것은 작동하지 않습니다와 내가 잘못 정확히 알아낼 수 없었습니다 :

List<int> inst = new List<int>();
int index = 0;
while (index < source.LastIndexOf("extract\"(me,i-have lots. of]punctuation", 0) + 39)
{
    int src = source.IndexOf("extract\"(me,i-have lots. of]punctuation", index);
    inst.Add(src);
    index = src + 40;
}
  • inst = 목록
  • source = 큰 문자열

더 좋은 아이디어가 있습니까?

답변

다음은 이에 대한 확장 방법의 예입니다.

public static List<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    List<int> indexes = new List<int>();
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            return indexes;
        indexes.Add(index);
    }
}

이것을 정적 클래스에 넣고를 사용하여 네임 스페이스를 가져 using오면 모든 문자열에 대한 메서드로 표시되며 다음과 같이 할 수 있습니다.

List<int> indexes = "fooStringfooBar".AllIndexesOf("foo");

확장 방법에 대한 자세한 내용은 http://msdn.microsoft.com/en-us/library/bb383977.aspx 를 참조하십시오 .

반복자를 사용하여도 동일합니다.

public static IEnumerable<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            break;
        yield return index;
    }
}

답변

내장 된 RegEx 클래스를 사용하지 않는 이유 :

public static IEnumerable<int> GetAllIndexes(this string source, string matchString)
{
   matchString = Regex.Escape(matchString);
   foreach (Match match in Regex.Matches(source, matchString))
   {
      yield return match.Index;
   }
}

표현식을 재사용해야하는 경우 컴파일하고 어딘가에 캐시하십시오. 재사용 사례에 대한 다른 오버로드에서 matchString 매개 변수를 Regex matchExpression으로 변경합니다.

답변

LINQ 사용 

public static IEnumerable<int> IndexOfAll(this string sourceString, string subString)
{
    return Regex.Matches(sourceString, subString).Cast<Match>().Select(m => m.Index);
}

답변

세련된 버전 + 지원을 무시하는 케이스 :

public static int[] AllIndexesOf(string str, string substr, bool ignoreCase = false)
{
    if (string.IsNullOrWhiteSpace(str) ||
        string.IsNullOrWhiteSpace(substr))
    {
        throw new ArgumentException("String or substring is not specified.");
    }

    var indexes = new List<int>();
    int index = 0;

    while ((index = str.IndexOf(substr, index, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)) != -1)
    {
        indexes.Add(index++);
    }

    return indexes.ToArray();
}

답변

O (N + M)에서 KMP 알고리즘을 사용하여 효율적인 시간 복잡도로 수행 할 수 있습니다. 여기서 N은 길이 text이고 M은 길이입니다.pattern .

이것은 구현 및 사용법입니다.

static class StringExtensions
{
    public static IEnumerable<int> AllIndicesOf(this string text, string pattern)
    {
        if (string.IsNullOrEmpty(pattern))
        {
            throw new ArgumentNullException(nameof(pattern));
        }
        return Kmp(text, pattern);
    }

    private static IEnumerable<int> Kmp(string text, string pattern)
    {
        int M = pattern.Length;
        int N = text.Length;

        int[] lps = LongestPrefixSuffix(pattern);
        int i = 0, j = 0;

        while (i < N)
        {
            if (pattern[j] == text[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                yield return i - j;
                j = lps[j - 1];
            }

            else if (i < N && pattern[j] != text[i])
            {
                if (j != 0)
                {
                    j = lps[j - 1];
                }
                else
                {
                    i++;
                }
            }
        }
    }

    private static int[] LongestPrefixSuffix(string pattern)
    {
        int[] lps = new int[pattern.Length];
        int length = 0;
        int i = 1;

        while (i < pattern.Length)
        {
            if (pattern[i] == pattern[length])
            {
                length++;
                lps[i] = length;
                i++;
            }
            else
            {
                if (length != 0)
                {
                    length = lps[length - 1];
                }
                else
                {
                    lps[i] = length;
                    i++;
                }
            }
        }
        return lps;
    }

그리고 이것은 그것을 사용하는 방법의 예입니다 :

static void Main(string[] args)
    {
        string text = "this is a test";
        string pattern = "is";
        foreach (var index in text.AllIndicesOf(pattern))
        {
            Console.WriteLine(index); // 2 5
        }
    }

답변

public List<int> GetPositions(string source, string searchString)
{
    List<int> ret = new List<int>();
    int len = searchString.Length;
    int start = -len;
    while (true)
    {
        start = source.IndexOf(searchString, start + len);
        if (start == -1)
        {
            break;
        }
        else
        {
            ret.Add(start);
        }
    }
    return ret;
}

다음과 같이 호출하십시오.

List<int> list = GetPositions("bob is a chowder head bob bob sldfjl", "bob");
// list will contain 0, 22, 26

답변

@Matti Virkkunen의 좋은 답변

public static List<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    List<int> indexes = new List<int>();
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            return indexes;
        indexes.Add(index);
        index--;
    }
}

그러나 이것은 AOOAOOA와 같은 테스트 케이스를 다룹니다.

AOOA 및 AOOA

출력 0 및 3