字符串匹配

朴素匹配

#include <stdio.h>
#include <string.h>

int main()
{
    cahr s1[]="abcbbacb";
    char s2[]="ba";
    printf("%p\n",strstr(s1,s2));

    return 0;
}

匹配不上就后挪

#include <stdio.h>
#include <string.h>
int strMatch(char* str,char* pattern)
{
    int n=strlen(str);
    int m=strlen(pattern);
    
    for(int i=0;i<=(n-m);i++)
    {
        int j=0;
        while (j<m)
        {
            if(str[i]==pattern[j])
            {
                i++;
                j++;
            }
            else                    //不等则后移
            {
                i=i-j;
                break;
            }
        }
        if(j==m)
        {

            return i-j;
        }
    }
    return -1;
}


int main()
{
    char* str ="abcabaabcabc";
    char* pattern ="abaa";
    int pos =strMatch(str,pattern);
    printf("%d\n",pos);
    return 0;
}

KMP匹配

#include<stdio.h>
#include<string.h>

void getNext(char* pattern,int* next)
{
    int m=strlen(pattern);
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<m)
    {
        if(j==-1||pattern[i]=pattern[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
}

int kmp(char*str,cahr* pattern)
{
    int i=0;
    int j=0;
    int next[100]
    getNext(pattern,next);
    int n=strlen(str);
    int m=strlen(pattern);

    while(i<n&&j<m)
    {
        if(j==-1||str[i]==pattern[j])
        {
            i++;
            j++;
        }
        else     
        {
            j=next[j];
        }
    }
    
    if(j==m)
    {
        return i-j;
    }
    else
    {
        return -1;
    }

}       
            

int main()
{
    char* str="abaabaabacacaabaabcc;
    char* pattern=ababc;
    printf("%d\n",kmp(str,pattern));
    return 0;
}

二维数组

按行优先排列

按列优先排列

特殊矩阵