動態規劃題,要掃描比較字符串

定義dp[i]爲串S中從第i位開始的串的最長前綴的長度,根據題目要求,結果輸出 dp[0] (從第0位開始到len(S)-1的串的最長前綴的長度)

定義fd(i)爲//主串S中以第i位開始的字串,向後比較匹配集合中元素的最大長度

倒序遞推: 從i=lens-1 到 i=0

• fd(i)=0
• dp [i]=0
• fd(i)=k(k>0)
• dp [i]=dp[i+j]+j (1<=j<=k-1;dp[i+j]!=0)
• 如果不滿足上式dp [i]=dp[i+k]+k

/*
ID: cmykrgb1
PROG: prefix
LANG: C++
*/
#include <stdio.h>
#include <string.h>
#define maxl 200201
FILE *fi,*fo;

typedef struct
{
    char w[11];
    int len;
} dic;

dic p[201];
char s[maxl];
long int lenp,lens;
long int dp[maxl];

void readfile(void)
{
    char c,lc=0;
    int i=0,j=0;
    while ((c=getc(fi))!='.')
    {
        if (c>='A' && c<='Z')
        {
            if (!(lc>='A' && lc<='Z'))
                i++;
            p[i].w[j++]=c;    
        }
        else 
            if (p[i].len==0)
            {
                p[i].len=j;
                j=0;
            }
        lc=c;
    }
    lenp=i;
    j=0;
    while ((c=getc(fi))!=EOF)
        if (c>='A' && c<='Z')
            s[j++]=c;
    lens=j;
    fclose(fi);
}

long int fd(long int k) //從第k位開始向後比較p[*].len位判斷有無匹配
{
    int i,j;
    for (j=lenp;j>=1;j--)
    {
        if (p[j].w[0]==s[k])
        {
            for (i=1;i<=p[j].len-1;i++)
                if (p[j].w[i]!=s[k+i])
                    goto next;
            return p[j].len;
        }
next:;
    }
    return 0;
}

void dynamic(void)
{

    long int i,j,k;
    dp[lens-1]=fd(lens-1);
    for (i=lens-2;i>=0;i--)
    {
        k=fd(i);
        if (k==0)
            dp[i]=0;
        else
        {
            if (dp[i+1]==0)
            {
                for (j=2;j<=k-1;j++)
                    if (dp[i+j]!=0)
                    {
                        dp[i]=dp[i+j]+j;
                        goto next2;
                    }
                dp[i]=dp[i+k]+k;
            }
            else
                dp[i]=dp[i+1]+1;
        }
next2:;
    }
}

void ssort(void)
{
    int i,j,min,m;
    char tstr[10];
    for (i=1;i<=lenp-1;i++)
    {
        min=11;
        for (j=i+1;j<=lenp;j++)
            if (p[j].len<min)
            {
                min=p[j].len;
                m=j;
            }
        if (p[i].len>p[m].len)
        {
            strcpy(tstr,p[i].w);
            strcpy(p[i].w,p[m].w);
            strcpy(p[m].w,tstr);
            min=p[i].len;
            p[i].len=p[m].len;
            p[m].len=min;
        }
    }
}

int main(void)
{
    fi=fopen("prefix.in","r");
    fo=fopen("prefix.out","w");
    readfile();
    ssort();
    dynamic();
    fprintf(fo,"%ldn",dp[0]);
    fclose(fo);
    return 0;
}