#2327557

Solution for ALDS1_14_B: String Search by chakku

Source Code Status Test Cases
    Policy: public     Reviewed: 1    
01.01 sec    3868 KB    60 lines     1745 bytes    2017-05-20 02:50
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define mp make_pair
#define pb push_back
#define EB emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr double eps = 1e-14; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    string t,p;
    cin >> t >> p;
    map<char,int> dict;
    int np = sz(p), nt=sz(t);
    rep(i,sz(p)-1){
        dict[p[i]] = np-1-i;
    }


    rep(i,sz(t)){
        int tail = i+np-1;
        if(tail>=nt){
            break;
        }
        if(p[np-1] == t[tail]){
            if(t.substr(i,np) == p) cout << i << endl;
        }

        int skip;
        if(dict[t[tail]]==0) skip = np-1;
        else skip = dict[t[tail]]-1;

        i += skip;
    }
    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 32/36 C++14 CPU: 01.01 sec Memory: 3868 KB Length: 1745 B 2017-05-20 02:50 2017-05-20 02:50
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3184 KB
Case #2: : Accepted 00.00 sec 3184 KB
Case #3: : Accepted 00.00 sec 3180 KB
Case #4: : Accepted 00.00 sec 3000 KB
Case #5: : Accepted 00.00 sec 3112 KB
Case #6: : Accepted 00.00 sec 3112 KB
Case #7: : Accepted 00.00 sec 3108 KB
Case #8: : Accepted 00.00 sec 3112 KB
Case #9: : Accepted 00.00 sec 3144 KB
Case #10: : Accepted 00.00 sec 3152 KB
Case #11: : Accepted 00.00 sec 3012 KB
Case #12: : Accepted 00.00 sec 3212 KB
Case #13: : Accepted 00.00 sec 3160 KB
Case #14: : Accepted 00.00 sec 3156 KB
Case #15: : Accepted 00.00 sec 3052 KB
Case #16: : Accepted 00.00 sec 3264 KB
Case #17: : Accepted 00.00 sec 3152 KB
Case #18: : Accepted 00.05 sec 3748 KB
Case #19: : Accepted 00.06 sec 3800 KB
Case #20: : Accepted 00.02 sec 3820 KB
Case #21: : Accepted 00.14 sec 3800 KB
Case #22: : Accepted 00.02 sec 3808 KB
Case #23: : Accepted 00.22 sec 3784 KB
Case #24: : Accepted 00.03 sec 3860 KB
Case #25: : Accepted 00.02 sec 3860 KB
Case #26: : Accepted 00.13 sec 3748 KB
Case #27: : Accepted 00.10 sec 3868 KB
Case #28: : Accepted 00.03 sec 3800 KB
Case #29: : Accepted 00.02 sec 3724 KB
Case #30: : Accepted 00.00 sec 3020 KB
Case #31: : Accepted 00.00 sec 3000 KB
Case #32: : Accepted 00.00 sec 3068 KB
Case #33: : Time Limit Exceeded 01.01 sec 3724 KB
Case #34: - - -
Case #35: - - -
Case #36: - - -
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags