HDU 3925 Substring

?题意：a串最少加上多少包含b串

解题思路：b从 ?x1 ? x10 x100 ? 直到乘到比a的串长一位 ? ?x的这个就是b串后面补零就行 ?

然后 ?用b-a ? ?如果b小于a ?则在b的前面补1再减a ? 得到的数和minn比较 ? 保存小的一个 ? ? ? 例如 ? ?b = 4 ?a = 5; ?b < a ? ?r = 14 - 5; ? ? 等于的判断不用 ? 因为前面匹配判断已经排除了这种情况

这里也许你会想到有前导零的情况 ? ?可以肯定输入数据是没有前导零的 ? ? 我已经试过了 ? 如果有前导零的情况 ? 代码就要做相应的修改了?

#include<cstdio>
#include<cstring>
#include<algorithm>

void sub(char *s,char *t,char *ch)//大数减法
{
    char p[105];
    memset(p,sizeof(p));
    int p_len = 0;
    int s_len = strlen(s);
    int t_len = strlen(t);
    int c = 0;
    for(int i = s_len-1,j = t_len-1; i >= 0; j--,i--)
    {
        int temp;
        if(j >= 0)
            temp = (s[i] -'0') - (t[j]-'0') + c;
        else temp = s[i] - '0' + c;
        if(temp < 0)
        {
            p[p_len++] = temp + 10 + '0';
            c = -1;
        }
        else
        {
            p[p_len++] = temp + '0';
            c = 0;
        }
    }
    int i = p_len -1;
    for( ; p[i] == '0'; i--);
    int k;
    for(k = 0; k <= i ;k ++)
        ch[k] = p[i - k];
    ch[k] = '';
}

int  Judge(char *str,char *t)
{
    int s_len = strlen(str);
	int t_len = strlen(t);
	int flag = 0;
	for(int i = 0; i <= s_len-t_len && !flag ; i++)
    {
        int ok = 1;
        for(int j = 0; j < t_len; j++)
        {
	       	if(str[i+j] != t[j])
            {ok = 0;break;}
   	    }
   	    if(ok)flag = 1;
    }
	if(flag )return 1;
	else return 0;
}

void  get_s(char *str,int l,char *s)//从str串中截取和t串长度数位相同的串
{
    int s_len = 0;
    int str_len = strlen(str);
    for(int t = str_len - l; t < str_len; t++)
        s[s_len++] = str[t];
    s[s_len] = '';
}

int CMP(char *a,char *b)
{
    int a_len = strlen(a);
    int b_len = strlen(b);
    if(a_len < b_len)return -1;
    if(a_len > b_len)return 1;
    for(int i = 0; i < a_len; i++)
        if(a[i] < b[i])return -1;
        else if(a[i] > b[i])return 1;
    return 0;
}

/*void clear_zero(char *s)
{
    int s_len = strlen(s);
    int i,j,t_len = 0;
    char t[105];
    for(i = 0; s[i] == '0'&& i < s_len -1 ; i++);
    for(j = i; j < s_len; j++)
        t[t_len++] = s[j];
        t[t_len] = '';
    strcpy(s,t);
}*/

int main()
{
    //freopen("in.txt","r",stdin);
	int N;
	scanf("%d",&N);
	for(int k = 1; k <= N; k++)
    {
        char str[105],s[105],result[105],t[105],p[105],num[105];
        char minn[105] = "1000000000000000";
		getchar();
	    scanf("%s%s",str,t);
	   // clear_zero(str);
	   // puts(str);
	    //clear_zero(t);
	    //puts(t);
	    printf("Case #%d: ",k);
	    int flag = CMP(str,t);//str 大于 t 返回 1，等于返回0  小于返回 -1
	    //printf("flag = %dn",flag);
	    if(flag < 0)
        {
            sub(t,result);
            printf("%sn",result);
        }
        else if(flag == 0 || Judge(str,t))printf("0n");
        else
        {
            int str_len = strlen(str);
            int t_len = strlen(t);
            int num_len = 1;
            num[0] = '1';
            for(int i = 1; i < t_len+1; i++)
                num[num_len++] = '0';
            num[num_len] = '';
            int ok;
            for(int i = t_len; i < str_len + 2; i++)
            {
                if(i < str_len +1)get_s(str,i,s);
                //printf("i = %dns = %sn",s);
               // printf("t = %sn",t);
                ok = CMP(t,s);
                if(ok < 0)
                {
                    sub(s,t,p);
                   // printf("n = %sn",num);
                   // printf("p = %sn",p);
                    sub(num,p,result);
                }
                else
                    sub(t,s,result);
               // printf("r = %sn",result);
                if(CMP(result,minn) < 0)
                    strcpy(minn,result);
                //printf("m = %snn",minn);
                num[num_len++]  = t[t_len++] = '0';
                num[num_len] = t[t_len] = '';
            }
            printf("%sn",minn);
        }
	}
	return 0;
}