确定这道题标签没有错?

测试数据 #0: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #1: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #2: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #7: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #10: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #11: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #12: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #13: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #14: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #15: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #16: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #17: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #18: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #19: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #20: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #21: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #22: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #23: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #24: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #25: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #26: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #27: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #28: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #29: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #30: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #31: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #32: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #33: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #34: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #35: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #36: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #37: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #38: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #39: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

kmp做法,数组开小了就爆,开大了就超,确定可以用KMP?我记得M67大神说了不可以的

3 条评论

  • @ 2016-10-24 22:34:42
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    
    char a[6000005];
    int kmp[205];
    char inp[205];
    int size;
    
    void getkmp()
    {
        kmp[0] = 1;
        kmp[1] = 1;
        int i = 2;
        int k = 1;
        int temp = 1;
        while (i <= size)
        {
            if(inp[i] == inp[k])
            {
                kmp[i] = temp;
                ++i;
                ++k;
            }
            else
            {
                while(inp[i] != inp[k] && k > 0)
                {
                    temp += kmp[k];
                    k -= kmp[k];
                }
                kmp[i] = temp;
                ++i;
                ++k;
            }
        }
    }
    
    int main()
    {
        int i = 1;
        while(scanf("%c",&inp[i]))
        {
            if(inp[i] == '\n')
            {
                break;
            }
            ++i;
            //printf("success\n");
        }
        size = i - 1;
        getkmp();
        /*for(int j = 1;j <= size;++j)
        {
            printf("%d ",kmp[j]);
        }*/
        int k = 1,temp;
        for(int j = 1;j < 10;++j)
        {
            a[k] = '0' + j;
            ++k;
        }
        for(int j = 10;j < 100;++j)
        {
            temp = j;
            a[k] = '0' + temp / 10;
            ++k;
            temp %= 10;
            a[k] = '0' + temp;
            ++k;
        }
        for(int j = 100;j < 1000;++j)
        {
            temp = j;
            a[k] = '0' + temp / 100;
            ++k;
            temp %= 100;
            a[k] = '0' + temp / 10;
            ++k;
            temp %= 10;
            a[k] = '0' + temp;
            ++k;
        }
        for(int j = 1000;j < 10000;++j)
        {
            temp = j;
            a[k] = '0' + temp / 1000;
            ++k;
            temp %= 1000;
            a[k] = '0' + temp / 100;
            ++k;
            temp %= 100;
            a[k] = '0' + temp / 10;
            ++k;
            temp %= 10;
            a[k] = '0' + temp;
            ++k;
        }
        for(int j = 10000;j < 100000;++j)
        {
            temp = j;
            a[k] = '0' + temp / 10000;
            ++k;
            temp %= 10000;
            a[k] = '0' + temp / 1000;
            ++k;
            temp %= 1000;
            a[k] = '0' + temp / 100;
            ++k;
            temp %= 100;
            a[k] = '0' + temp / 10;
            ++k;
            temp %= 10;
            a[k] = '0' + temp;
            ++k;
        }
        for(int j = 100000;j < 1000000;++j)
        {
            temp = j;
            a[k] = '0' + temp / 100000;
            ++k;
            temp %= 100000;
            a[k] = '0' + temp / 10000;
            ++k;
            temp %= 10000;
            a[k] = '0' + temp / 1000;
            ++k;
            temp %= 1000;
            a[k] = '0' + temp / 100;
            ++k;
            temp %= 100;
            a[k] = '0' + temp / 10;
            ++k;
            temp %= 10;
            a[k] = '0' + temp;
            ++k;
        }
        //printf("print start\n");
        /*for(int j = 1;j <= 1000;++j)
        {
            printf("%c ",a[j]);
        }*/
        //printf("\n%d",size);
        i = 0;
        k = 0;
        while(k < size)
        {
            if(a[i + 1] == inp[k + 1])
            {
                //printf("%d matched!\n",i + 1);
                i += 1;
                k += 1;
            }
            else
            {
                if(k == 0)
                {
                    i += 1;
                    continue;
                }
                k -= kmp[k];
            }
        }
        printf("%d" ,i - size + 1);
        //system("pause");
        return 0;
    }
    

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 6428 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 6412 KiB, score = 0
    测试数据 #9: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #10: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #11: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #12: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
    测试数据 #13: Accepted, time = 0 ms, mem = 6424 KiB, score = 10
    测试数据 #14: Accepted, time = 0 ms, mem = 6424 KiB, score = 10
    测试数据 #15: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #16: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
    测试数据 #17: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #18: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #19: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #20: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #21: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
    测试数据 #22: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
    测试数据 #23: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
    测试数据 #24: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
    测试数据 #25: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
    测试数据 #26: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
    测试数据 #27: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
    测试数据 #28: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
    测试数据 #29: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
    测试数据 #30: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
    测试数据 #31: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #32: RuntimeError, time = 31 ms, mem = 6424 KiB, score = 0
    测试数据 #33: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
    测试数据 #34: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
    测试数据 #35: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
    测试数据 #36: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
    测试数据 #37: RuntimeError, time = 31 ms, mem = 6424 KiB, score = 0
    测试数据 #38: RuntimeError, time = 31 ms, mem = 6420 KiB, score = 0
    测试数据 #39: Accepted, time = 0 ms, mem = 6428 KiB, score = 10
    TimeLimitExceeded, time = 1668 ms, mem = 6428 KiB, score = 220
    同KMP
    22个点
    求大牛为何RTE

  • @ 2016-08-13 21:54:32

    同感,好整齐的时间

  • @ 2013-03-05 21:03:21

    夷,这么整齐的时间和内存很少见。

  • 1

信息

ID
1005
难度
8
分类
字符串 | KMP 点击显示
标签
(无)
递交数
6659
已通过
634
通过率
10%
被复制
33
上传者