NKEDIT - Hiệu chỉnh văn bản

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include <conio.h>

using namespace std;

void FailureFunction(char P[],int F[],int m)
{
     int i,j;
     F[0] = 0;
     j = 0;
     i = 1;
     while(i<m)
     {
         if(P[i] == P[j])
         {
             F[i] = j+1;
             i++;
             j++;
         }
         else if(j>0)
             j = F[j-1];
         else
         {
             F[i] = 0;
             i++;
         }
     }
}

int KMP(int n,char T[],int m, char P[])
{
    int i,j,F[100];
    FailureFunction(P,F,m);
    i = 0;
    j = 0;
    while(i<n)
    {
        if(T[i] == P[j])
        {
            if(j == m-1)
                 return i-j;
            else
            {
                i++;
                j++;
            }
        }
        else if(j>0)
            j = F[j-1];
        else i++;
    }
    return -1;
}

int main()
{
   // freopen("NKEDIT.in","r",stdin);
    int k,n,m,chay=0;
    char s[52],p[52],the[52];
    scanf("%d",&k);
    scanf("%s %s",s,p);
    n = strlen(s); m = strlen(p);
    while(true)
    {
        int flag = 0;
        for(int i = n;i>=k;i--)
        {
            for(int j = 0;j<=n-i;j++)
            {
                for(int k = 0;k<=i-1;k++)
                    the[k] = s[k+j];
                int pos = KMP(m,p,i,the);
                if(pos!=-1)
                {
                    chay++;
                    flag = 1;
                    for(int k = j;k<=n-i-1;k++)
                        s[k] = s[k+i];
                    for(int k = pos;k<=m-i-1;k++)
                       p[k] = p[k+i];
                    n = n-i;
                    m = m-i;
                }
                if( flag ==1)
                    break;
            }
            if(flag == 1)
                break;
        }
        if(flag ==0)
            break;
    }
    printf("%d\n",chay);
    for(int i = 0;i<n;i++)
        printf("%c",s[i]);
    printf("\n");
    for(int i = 0;i<m;i++)
        printf("%c",p[i]);
    //getch();
}

Download