Submission #7533383


Source Code Expand

Copy
// A C++ program that implements Z algorithm for pattern searching
#include<iostream>
using namespace std;
void getZarr(string str, int Z[])
{
    int n = str.length();
    int L, R, k;
    L = R = 0;
    for (int i = 1; i < n; ++i)
    {
        if (i > R)
        {
            L = R = i;
            while (R<n && str[R-L] == str[R])
                R++;
            Z[i] = R-L;
            R--;
        }
        else
        {
            k = i-L;
            if (Z[k] < R-i+1)
                Z[i] = Z[k];
            else
            {
                L = i;
                while (R<n && str[R-L] == str[R])
                    R++;
                Z[i] = R-L;
                R--;
            }
        }
    }
}
bool srch(string concat,int r)
{
    int l = concat.length();
    int Z[l];
    getZarr(concat, Z);
    for (int i = 0; i < l; ++i)
    {
        if (Z[i] == r)
            return 1;
    }
    return 0;
}
int main()
{
    int n,ans=0;
    string a,b;
    cin>>n>>a;
    for(int i=0; i<n; i++){
        for(int j=ans;; j++){
            if(j>=a.size()) break;
            b=a;
            b.insert(b.begin()+j+1,'#');
            if(srch(b,j+1)){
                ans++;
            }else{
                break;
            }
        }
        a.erase(a.begin());
    }
    cout<<ans;
}

Submission Info

Submission Time
Task E - Who Says a Pun?
User ansisg
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1374 Byte
Status WA
Exec Time 138 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 1
WA × 2
AC × 53
WA × 17
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 01-handmade-12, 02-binary-13, 02-binary-14, 02-binary-15, 02-binary-16, 02-binary-17, 02-binary-18, 02-binary-19, 02-binary-20, 02-binary-21, 02-binary-22, 02-binary-23, 03-BigRandom-24, 03-BigRandom-25, 03-BigRandom-26, 03-BigRandom-27, 03-BigRandom-28, 03-BigRandom-29, 03-BigRandom-30, 03-BigRandom-31, 03-BigRandom-32, 03-BigRandom-33, 03-BigRandom-34, 03-BigRandom-35, 03-BigRandom-36, 03-BigRandom-37, 03-BigRandom-38, 03-BigRandom-39, 03-BigRandom-40, 03-BigRandom-41, 03-BigRandom-42, 03-BigRandom-43, 03-BigRandom-44, 03-BigRandom-45, 03-BigRandom-46, 03-BigRandom-47, 03-BigRandom-48, 03-BigRandom-49, 03-BigRandom-50, 03-BigRandom-51, 03-BigRandom-52, 03-BigRandom-53, 03-BigRandom-54, 04-zero-55, 04-zero-56, 05-AllRandom-57, 05-AllRandom-58, 05-AllRandom-59, 05-AllRandom-60, 05-AllRandom-61, 05-AllRandom-62, 05-AllRandom-63, 05-AllRandom-64, 05-AllRandom-65, 05-AllRandom-66, 05-AllRandom-67, 05-AllRandom-68, 05-AllRandom-69
Case Name Status Exec Time Memory
00-sample-00 WA 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 WA 1 ms 256 KB
01-handmade-03 AC 138 ms 256 KB
01-handmade-04 AC 132 ms 256 KB
01-handmade-05 AC 70 ms 256 KB
01-handmade-06 AC 72 ms 256 KB
01-handmade-07 AC 72 ms 256 KB
01-handmade-08 AC 117 ms 256 KB
01-handmade-09 AC 89 ms 256 KB
01-handmade-10 AC 100 ms 256 KB
01-handmade-11 AC 121 ms 256 KB
01-handmade-12 AC 134 ms 256 KB
02-binary-13 AC 70 ms 256 KB
02-binary-14 AC 83 ms 256 KB
02-binary-15 AC 64 ms 256 KB
02-binary-16 AC 95 ms 256 KB
02-binary-17 AC 95 ms 256 KB
02-binary-18 AC 82 ms 256 KB
02-binary-19 AC 51 ms 256 KB
02-binary-20 AC 61 ms 256 KB
02-binary-21 AC 56 ms 256 KB
02-binary-22 AC 54 ms 256 KB
02-binary-23 AC 47 ms 256 KB
03-BigRandom-24 AC 60 ms 256 KB
03-BigRandom-25 AC 60 ms 256 KB
03-BigRandom-26 AC 55 ms 256 KB
03-BigRandom-27 AC 65 ms 256 KB
03-BigRandom-28 AC 51 ms 256 KB
03-BigRandom-29 AC 61 ms 256 KB
03-BigRandom-30 AC 50 ms 256 KB
03-BigRandom-31 AC 60 ms 256 KB
03-BigRandom-32 AC 62 ms 256 KB
03-BigRandom-33 AC 49 ms 256 KB
03-BigRandom-34 AC 67 ms 256 KB
03-BigRandom-35 AC 48 ms 256 KB
03-BigRandom-36 AC 66 ms 256 KB
03-BigRandom-37 AC 64 ms 256 KB
03-BigRandom-38 AC 57 ms 256 KB
03-BigRandom-39 AC 66 ms 256 KB
03-BigRandom-40 AC 54 ms 256 KB
03-BigRandom-41 AC 65 ms 256 KB
03-BigRandom-42 AC 63 ms 256 KB
03-BigRandom-43 AC 61 ms 256 KB
03-BigRandom-44 AC 56 ms 256 KB
03-BigRandom-45 AC 59 ms 256 KB
03-BigRandom-46 AC 50 ms 256 KB
03-BigRandom-47 AC 63 ms 256 KB
03-BigRandom-48 AC 62 ms 256 KB
03-BigRandom-49 AC 58 ms 256 KB
03-BigRandom-50 AC 63 ms 256 KB
03-BigRandom-51 AC 66 ms 256 KB
03-BigRandom-52 AC 63 ms 256 KB
03-BigRandom-53 AC 64 ms 256 KB
03-BigRandom-54 AC 66 ms 256 KB
04-zero-55 WA 1 ms 256 KB
04-zero-56 WA 1 ms 256 KB
05-AllRandom-57 WA 42 ms 256 KB
05-AllRandom-58 WA 38 ms 256 KB
05-AllRandom-59 WA 43 ms 256 KB
05-AllRandom-60 WA 41 ms 256 KB
05-AllRandom-61 WA 40 ms 256 KB
05-AllRandom-62 WA 40 ms 256 KB
05-AllRandom-63 WA 38 ms 256 KB
05-AllRandom-64 WA 38 ms 256 KB
05-AllRandom-65 WA 39 ms 256 KB
05-AllRandom-66 WA 40 ms 256 KB
05-AllRandom-67 WA 40 ms 256 KB
05-AllRandom-68 WA 43 ms 256 KB
05-AllRandom-69 WA 43 ms 256 KB