Если строка является итеративной подстрокой?

Ответ 1

Я могу думать об эвристике, но только вызов KMP на подстроке, если Len (исходная строка)/Len of (sub string) является положительным целым числом.

Также максимальная длина подстроки должна быть меньше N/2.

ИЗМЕНИТЬ

Используя эти эвристики, я написал следующий код python, потому что мой C ржавый в данный момент

oldstr='ABCDABCD'    

for i in xrange(0,len(oldstr)/2):
       newslice=oldstr[0:i+1]
         if newslice*(len(oldstr)/len(newslice)) == oldstr:
             print 'pattern found', newslice
             break

Ответ 2

Вам просто нужно заботиться о тестировании длины подстроки, которые равны полной длине строки , деленной на простое число. Причина в том, что если S содержит n копий T и n не является простым, то n = ab, и поэтому S фактически также содержит копии bT (где "bT" означает "T повторяется b раз" ). Это расширение anijhaw answer.

int primes[] = { 2, 3, 5, 7, 11, 13, 17 };  /* There are one or two more... ;) */
int nPrimes = sizeof primes / sizeof primes[0];

/* Passing in the string length instead of assuming ASCIIZ strings means we
 * don't have to modify the string in-place or allocate memory for new copies
 * to handle recursion. */
int is_iterative(char *s, int len) {
    int i, j;
    for (i = 0; i < nPrimes && primes[i] < len; ++i) {
        if (len % primes[i] == 0) {
            int sublen = len / primes[i];
            /* Is it possible that s consists of repeats of length sublen? */
            for (j = sublen; j < len; j += sublen) {
                if (memcmp(s, s + j, sublen)) {
                    break;
                }
            }

            if (j == len) {
                /* All length-sublen substrings are equal.  We could stop here
                 * (meaning e.g. "abababab" will report a correct, but
                 * non-minimal repeated substring of length 4), but let's
                 * recurse to see if an even shorter repeated substring
                 * can be found. */
                return is_iterative(s, sublen);
            }
        }
    }

    return len;     /* Could not be broken into shorter, repeated substrings */
}

Обратите внимание, что при повторном поиске, чтобы найти еще более короткие повторяющиеся подстроки, нам не нужно снова проверять всю строку, просто первое большее повторение - поскольку мы уже установили, что оставшиеся большие повторы являются, ну, повторениями первый.:)

Ответ 3

Я не вижу, что алгоритм KMP помогает в этом случае. Это не вопрос определения, с чего начать следующий матч. Кажется, что один из способов сократить время поиска - начать с самой длинной возможности (на половину длины) и работать вниз. Единственными длинами, которые нужно протестировать, являются длины, которые равномерно делятся на общую длину. Вот пример в Ruby. Я должен добавить, что я понимаю, что вопрос был помечен как C, но это был просто простой способ показать алгоритм, о котором я думал (и позволил мне проверить, что он сработал).

class String
def IsPattern( )
    len = self.length
    testlen = len / 2
    # the fastest is to start with two entries and work down
    while ( testlen > 0 )
        # if this is not an even divisor then it can't fit the pattern
        if ( len % testlen == 0 )
            # evenly divides, so it may match
            if ( self == self[0..testlen-1] * ( len / testlen ))
                return true
            end

        end
        testlen = testlen - 1
    end
    # must not have matched
    false
end
end

if __FILE__ == $0

   ARGV.each do |str|
       puts "%s, %s" % [str, str.IsPattern ? "true" : "false" ]
   end

end



[C:\test]ruby patterntest.rb a aa abab abcdabcd abcabcabc zzxzzxzzx abcd
a, false
aa, true
abab, true
abcdabcd, true
abcabcabc, true
zzxzzxzzx, true
abcd, false

Ответ 4

Я полагаю, вы могли бы попробовать следующий алгоритм:

Позволяет L быть возможной длиной подстроки, которая генерирует исходное слово. Для L от 1 до strlen(s)/2 проверьте, получает ли первый символ во всех позициях L*i для i от 1 до strlen(s)/L. Если это так, то это может быть возможным решением, и вы должны проверить его с помощью memcmp, если не попробовать следующий L. Конечно, вы можете пропустить некоторые значения L, которые не делятся на strlen(s).

Ответ 5

Попробуйте следующее:

    char s[] = "abcabcabcabc";
int nStringLength = strlen (s);
int nMaxCheckLength = nStringLength / 2;
int nThisOffset;
int nNumberOfSubStrings;
char cMustMatch;
char cCompare;
BOOL bThisSubStringLengthRepeats;
// Check all sub string lengths up to half the total length
for (int nSubStringLength = 1;  nSubStringLength <= nMaxCheckLength;  nSubStringLength++)
{
    // How many substrings will there be?
    nNumberOfSubStrings = nStringLength / nSubStringLength;

    // Only check substrings that fit exactly
    if (nSubStringLength * nNumberOfSubStrings == nStringLength)
    {
        // Assume it going to be ok
        bThisSubStringLengthRepeats = TRUE;

        // check each character in substring
        for (nThisOffset = 0;  nThisOffset < nSubStringLength;  nThisOffset++)
        {
            // What must it be?
            cMustMatch = s [nThisOffset];

            // check each substring char in that position
            for (int nSubString = 1;  nSubString < nNumberOfSubStrings;  nSubString++)
            {
                cCompare = s [(nSubString * nSubStringLength) + nThisOffset];
                // Don't bother checking more if this doesn't match
                if (cCompare != cMustMatch)
                {
                    bThisSubStringLengthRepeats = FALSE;
                    break;
                }
            }

            // Stop checking this substring
            if (!bThisSubStringLengthRepeats)
            {
                break;
            }
        }

        // We have found a match!
        if (bThisSubStringLengthRepeats)
        {
            return TRUE;
        }
    }
}

// We went through the whole lot, but no matches found
return FALSE;

Ответ 6

Это код Java, но вы должны понять:

        String str = "ababcababc";
    int repPos = 0;
    int repLen = 0;
    for( int i = 0; i < str.length(); i++ ) {
        if( repLen == 0 ) {
            repLen = 1;
        } else {
            char c = str.charAt( i );
            if( c == str.charAt( repPos ) ) {
                repPos = ++repPos % repLen;
            } else {
                repLen = i+1;
            }
        }
    }

Это вернет длину кратчайшего повторяющегося фрагмента или длины строки, если повторения не будет.

Ответ 7

Вы можете построить массив суффикса строки, отсортировать его.
Теперь найдите серию суффиксов с удвоением и когда вы достигли того, что размер всей строки (S) первый в серии даст вам T.

Например:

abcd <-- T
abcdabcd <-- S
bcd
bcdabcd
cd
cdabcd
d
dabcd

x
xzzx
xzzxzzx
zx
zxzzx
zxzzxzzx
zzx <-- T
zzxzzx
zzxzzxzzx <-- S

a
apa
apapa
apapapa
pa <-- T
papa
papapa <-- Another T, not detected by this algo
papapapa <-- S