#!/usr/bin/env python
 
#Last Change:  2010-11-03 13:38:36
def compute_prefix_function(p):
    '''
    compute_prefix_function(p) --> a list
 
    [p] is a pattern sequence to be searched in a longer sequence.
    '''
    m = len(p)
    pi = [] * m
    k = 
    for q in range(1, m):
        while k >  and p[k] != p[q]:
            k = pi[k - 1]
        if p[k] == p[q]:
            k = k + 1
        pi[q] = k
    return pi
 
def kmp_matcher(t, p):
    '''
    kmp_matcher(t, p) --> a list
 
    [t, p] is two sequences, which 'p' maybe partof 't'.
    '''
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 
    index = []
    for i in range(n):
        while q >  and p[q] != t[i]:
            q = pi[q - 1]
        if p[q] == t[i]:
            q = q + 1
        if q == m:
            q = 
            index.append(i-m+2)
    #-----end of for---------------------------
    return -1 if len(index) ==  else index
 
if __name__ == '__main__':
    str = "1230012123211212213012300121232112122130123001212321121221312300121232112122130"
    substr = "1212"
    #for i in range(10000000):
    #    kmp_matcher(str, substr)
    print kmp_matcher(str, substr)

def index(subseq, seq):
    '''''
    index(subseq, seq) -->a list of numbers or -1
    Return an index of [subseq] in the [seq].
    Or -1 if [subseq] is not a subsequence of [seq].
    The time complexity of the algorithm is O(n*m), where
    n, m = len(seq), len(subseq).
    >>>index('12', '0112')
    [2]
    >>>index([1,2], [011212])
    [2, 4]
    >>>index('13', '0112')
    -1
    '''
    i, n, m = -1, len(seq), len(subseq)
    index = []
    try:
        while True:
            i = seq.index(subseq[], i+1, n - m + 1)
            if subseq == seq[i:i+m]:
                index.append(i)
    except ValueError:
        return index if len(index) >  else -1
def subseqInSeq(subseq, seq):
    '''''
    subseqInSeq(subseq, seq) ---> list or -1
    The same as index.
    '''
    indexList = []
    m = len(subseq)
    subseqRepla = '*' * m
    while subseq[] in seq:
        index = seq.index(subseq[])
        if subseq == seq[index:index+m]:
            indexList.append(index)
            seq = seq.replace(subseq, subseqRepla, 1)
        else:
            seq = seq.replace(subseq[], '*', 1)
    return (indexList if len(indexList) >  else -1)
def main():
    print index('ab', 'abcdab')
    print subseqInSeq('ab', 'abcdab')

#include
#include
#include 
 
int kmp(char *substr, char *str, int *index);
int prefix(char *substr, int lensub, int *subIndex);
 
/* this is a string compare function using KMP */
int kmp(char *substr, char *str, int *index)
{
	int lensub, lenstr;
	int i = ;
	int q = ;
	int k = ; //a index of array-index
	lensub = strlen(substr);
	lenstr = strlen(str);
	int subIndex[lensub];
 
	prefix(substr, lensub, subIndex);
 
	for( i =  ; i < lenstr ; i++ )
	{
		while( (q > ) && (*(substr+q) != *(str+i)))
		{
			q = subIndex[q-1];
		}
		if( *(substr+q) == *(str+i) )
		{
			q++;
		}
		if( q == lensub )
		{
			q = subIndex[q-1];
			*(index+k) = i-lensub+2;//1 or 2
			k++;
		}
	}
	return ;
}
 
/* this does a self kmp of short string to get the prefix function */
int prefix(char *substr, int lensub, int *subIndex)
{
	int k = ;
	int q = ;
 
	for( q =  ; q < lensub ; q++ )
	{
		*(subIndex+q) = ;
	}
 
	for( q = 1 ; q < lensub ; q++ )
	{
		while( k >  && *(substr+k) != *(substr+q) )
		{
			k = subIndex[k-1];
		}
		if( *(substr+k) == *(substr+q) )
		{
			k++;
		}
		*(subIndex+q) = k;
	}
	return ;
}
 
int main(int argc, char *argv[])
{
	clock_t start, finish;
	start = clock();
	double duration;
	char *str = "CGTAACGCGTGCCGCGGCTACGTAACGCGGCTA";
 
	char *substr = "CGCG";
 
	int lenindex;
	lenindex = strlen(str)/strlen(substr);
	int index[lenindex];
	int i;
	for( i =  ; i < lenindex ; i++ )
	{
		index[i] = -1;
	}
 
	kmp(substr, str, &index[]);
 
	for( i =  ; i < lenindex ; i++ )
	{
		if( index[i] == -1 )
		{
			break;
		}
		printf("%d\n", index[i]);
	}
	finish = clock();
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("Done, %f seconds\n", duration);
 
	return ;
}

#include
#include
#include
#include 
 
typedef unsigned char byte;
 
int kmp(byte *bitsub, byte *bit, unsigned int lensub,
		unsigned int lenbit, unsigned int *index);
int prefix(byte *bitsub, unsigned int lensub, unsigned int *subIndex);
 
/* this is a string compare function using KMP */
int kmp(byte *bitsub, byte *bit, unsigned int lensub,
		unsigned int lenbit, unsigned int *index)
{
	unsigned int i = ;
	unsigned int q = ;
	unsigned int k = ; //a index of array-index
	unsigned int subIndex[lensub];
 
	prefix(bitsub, lensub, subIndex);
 
	for( i =  ; i < lenbit ; i++ )
	{
		while( (q > ) && (*(bitsub+q) ^ *(bit+i)))//*(bitsub+q) != *(bit+i))
		{
			q = subIndex[q-1];
		}
		if( !(*(bitsub+q) ^ *(bit+i)) )//*(bitsub+q) == *(bit+i))
		{
			q++;
		}
		if( !(q ^ lensub) ) //q == lensub
		{
			q = ;
			*(index+k) = i-lensub+2;
			k++;
		}
	}
 
	return ;
}
 
/* this does a self kmp of short string to get the prefix function */
int prefix(byte *bitsub, unsigned int lensub, unsigned int *subIndex)
{
	unsigned int k = ;
	unsigned int q = ;
 
	for( q =  ; q < lensub ; q++ )
	{
		*(subIndex+q) = ;
	}
 
	for( q = 1 ; q < lensub ; q++ )
	{
		while( k >  && (*(bitsub+k) ^ *(bitsub+q)) )//*(bitsub+k) != *(bitsub+q)
		{
			k = subIndex[k-1];
		}
		if(!(*(bitsub+k) ^ *(bitsub+q)))//*(bitsub+k) == *(bitsub+q) )
		{
			k++;
		}
		*(subIndex+q) = k;
	}
	return ;
}
 
int main(int argc, char *argv[])
{
 
	unsigned int i;
	struct timeval start;
	struct timeval finish;
	gettimeofday(&start, NULL);
 
	double duration;
	byte bit[79] = {1,2,3,,,1,2,1,2,3,2,1,1,2,1,2,2,1,3,,
		1,2,3,,,1,2,1,2,3,2,1,1,2,1,2,2,1,3,,1,2,3,,,1,2,
		1,2,3,2,1,1,2,1,2,2,1,3,1,2,3,,,1,2,1,2,3,2,1,1,2,1,2,2,1,3,};
	byte bitsub[4] = {1,2,1,2};
 
	unsigned int lenindex;
	unsigned int lenbit = sizeof(bit)/sizeof(byte);
	unsigned int lensub = sizeof(bitsub)/sizeof(byte);
	lenindex = lenbit/lensub;
	unsigned int index[lenindex];
	for( i =  ; i < lenindex ; i++ )
	{
		index[i] = ;
	}
	for( i =  ; i < 1000000 ; i++ )
	{
		kmp(bitsub, bit, lensub, lenbit, &index[]);
	}
 
	kmp(bitsub, bit, lensub, lenbit, &index[]);
 
	for( i =  ; i < lenindex ; i++ )
	{
		if( index[i] ==  )
		{
			break;
		}
		printf("%d\n", *(index+i));
	}
 
	gettimeofday(&finish, NULL);
 
	duration = (finish.tv_sec-start.tv_sec)
		+ (finish.tv_usec - start.tv_usec) / (1000000.1);
	printf("Done, %f seconds\n", duration);
 
	return ;
}