Begin: 2018-10-26 22:05 BST
Contest on Z algorithm
End: 2018-11-02 22:05 BST
168:00:00
Ended
Overview
Problem
Status
Rank (168:00:00)
0 Comments
Previous12345…Next
Username
Prob
    Result
    Time
(ms)    Mem
(MB)    Lang
    Submit Time
Sanjoy_Kumar
B
Accepted
2980
C++
5 months ago

All Copyright Reserved ©2018 Xu Han
Server Time: 2019-03-27 09:27:02 BST

#16750879 | Sanjoy_Kumar's solution for [UVA-10679] [Problem B]
Status
Accepted
Time
2980ms
Length
1256
Lang
C++11 5.3.0
Submitted
2018-10-31 02:07:19
RemoteRunId
22220819
Select Code
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);

using namespace std;

const int maxn = 2e6 + 10;

int main()
{
    fastio;
//    freopen("input.txt", "r", stdin);

    int test, q;
    cin >> test;

    while( test-- ){

        string line, in;
        cin >> line >> q;

        while( q-- ){

            cin >> in;
            int len = in.length();
            in = in + "#" + line;
            int sz = in.length();

            int lft, rgt, indx, maxLen = -1;
            int z[sz + 10] = {0};
            bool flag = true;
            lft = rgt = -1;

            for( int i = 1; i < sz; i++ ){
                if( i <= rgt )
                    z[i] = min( rgt - i + 1, z[i - lft]);
                while( (i + z[i] < sz) && (in[i + z[i]] == in[z[i]]) )
                    z[i]++;
                if( (i + z[i] - 1) > rgt ){
                    lft = i;
                    rgt = i + z[i] - 1;
                    if( z[i] == len ){
                        flag = false;
                        cout << "y" << endl;
                        break;
                    }
                }
            }
            if( flag ) cout << "n" << endl;
            in = "";
        }

        line = "";
    }

    return 0;
}