문자열 알 수없는 패턴 일치

s = 112468112468112468112468112468과 같은 문자열에서 알 수없는 패턴을 결정하고 싶습니다.

이 문자열에서 112468이 반복되는 패턴임을 분명히 알 수 있습니다. Google에서 을 검색했습니다. 일부 알고리즘을 찾는데 도움이되었지만 Boyer-Moore 알고리즘 등의 문자열에서 특정 패턴을 찾는 문자 만 볼 수있었습니다.

알 수없는 패턴이 4 리터의 비교 창을 사용하여 주어진 문자열에 대한 작동하지만, 그것은 아주 잘 다른 문자열을 작동하지 않을 수 있습니다

for(i=0;i<Length of String;i++) 
{ 
    for(j=i+1;j<Length of String;j++) 
    { 
    if(s[i]==s[j] && s[i+1]==s[j+1] && s[i+2]==s[j+2] && s[i+3]==s[j+3]) 
    { 
     patternlength=j-i; 

      for(k=i;k<j;k++) 
      { 
      pattern[k]=s[i+k] 
      } 
    } 
    } 
}

점이다. 아무도 더 나은 해결책을 알고 있습니다.

감사

출처

2012-02-20 Goku

기계에서 텍스트의 패턴을 식별하는 것은 쉬운 문제는 아닙니다. ** 예를 들어 반복되는 패턴이있는 문자열에만 ** 관심이 있습니까? 검색에 관심이있는 ** 유형 ** 또는 패턴 또는 패턴을 제공 할 수 있다면 더 많은 도움을 드릴 수 있습니다. – jefflunt

글쎄, 내가 다루고있는 패턴의 종류는 반복되는 패턴을 가진 문자열이 될 것이고, 위에서 "s"로 작성한 것과 매우 비슷할 것이다. 위의 코딩 된 메서드는 내게 잘 juss 작동합니다. 그러나 이것을 수행하기위한 표준 알고리즘이 있는지 알고 싶었습니다. – Goku

근본적으로 상이하고 잠재적으로 훨씬 어렵이이 패턴을 패턴 매칭되어 있지 않으며 인식.

그러나,이 스트링에 의해 나타나는 패턴의 간단한 종류 (Python 코드)를 사용하여 발견 된 수 :

def find_repeated_pattern(s): 
    for i in xrange(1, len(s)/2): 
     if s == s[:i] * (len(s)/i): 
      return s[:i]

이 때문에 모든 문자열 복사 순진 구현이지만, 그것은을 만들 수 있습니다 O (n ²) 시간 및 일정한 공간에서 작업하십시오.

출처

2012-02-20 22:29:16

안녕하세요. 답장을 보내 주셔서 감사합니다. 실제로 패턴을 찾기로되어있는 문자열도 동적으로 생성됩니다. 나는 파이썬 전문가가 아니지만이 코드 스 니펫이 어떤 종류의 문자열에 대해서 작동하는지는 필자가 작성한 코드와 동일하다. – Goku

문자열 알 수없는 패턴 일치

답변

관련 문제