strkmp.cpp

微软面试题：给出一个函数来输出一个字符串的所有排列。 简单的回溯就可以实现了。当然排列的产生也有很多种算法

// strkmp.cpp : Defines the entry point for the console application.
//

#include <iostream.h> 
#include <stdafx.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void kmp_init(const char *patn, int len, int *next)
{
        int i, j;

        assert(patn != NULL && len > 0 && next != NULL);
        next[0] = 0;
        for (i = 1, j = 0; i < len; i ++) {
                while (j > 0 && patn[j] != patn[i])
                        j = next[j - 1];
                if (patn[j] == patn[i])
                        j ++;
                next[i] = j;
        }
}

int kmp_find(const char *text, int text_len, const char *patn,
                int patn_len, int *next)
{
        int i, j;

        assert(text != NULL && text_len > 0 && patn != NULL && patn_len > 0
                        && next != NULL);
        for (i = 0, j = 0; i < text_len; i ++ ) {
                while (j > 0 && text[i] != patn[j])
                        j = next[j - 1];
                if (text[i] == patn[j])
                        j ++;
                if (j == patn_len)
                        return i + 1 - patn_len;
        }

        return -1;
}

static const char* _strstr(const char* s1, const char* s2)
{
     assert(s2 && s1);
	 int i;
     const char* p=s1, *r=s2;
     while(*p!='\0')
     {
		  i=0;
          while(*p++==*r++)
		  {
			i++;
            if(*r=='\0')
               return p-i;
		  }
          r=s2;
          p=++s1;

     }
     return NULL;
}


int main(int argc, char *argv[])
{
        int *next;
        int i, pos, len;
		char str1[300];
		char str[100];

        sprintf(str1, "UsaUsage UsaUa: UsaUs100 teUsUsaUgext patUsaUstern");
        sprintf(str, "UsUsaUge");
        len = strlen(str);
        next = (int*)calloc(300, sizeof(int));
        kmp_init(str, strlen(str), next);
        printf("next array:\n");
        for (i = 0; i < len; i ++)
                printf("\t%c", str[i]);
        printf("\n");
        for (i = 0; i < len; i ++)
                printf("\t%d", next[i]);
        printf("\n");

        pos = kmp_find(str1, strlen(str1), str, strlen(str), next);
        printf("find result:\n");
        if (pos < 0) {
                printf("None found!\n");
        } else {
                printf("%s\n", str1);
                for (i = 0; i < pos; i ++)
                        printf(" ");
                for (i = 0; i < len; i ++)
                printf("^");
        }

        char*p;
		p=strstr(str1,str);
        if(p)
          printf("\n%s\n",p);
        else
          printf("Not Found!");
		const char *pp=_strstr(str1,str);
        if(pp)
          printf("%s\n",pp);
        else
          printf("Not Found!");


        return 0;
}