Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HackerRank - Stryker world code sprint - C++ code study - computer professor, most competitive programmer in the world
#define BUFSIZE 1000000
char buf[BUFSIZE];
int Tests, cnum;
// #define USEWIN
#define MANYTESTS 0
#define LINEBYLINE
#include <algorithm>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;
typedef vector<string> vs;
#define LS <
#define Size(x) (int(x.size()))
// All macros with parameters "k,a,b" run the "k" variable in range [a,b)
#define FOR(k,a,b) for(__typeof(a) k=(a); k LS (b); ++k)
// parse a space-delimited string into a vs
vs parsevs(string s) {
s = s + " ";
string q = "";
vs res;
FOR(l,0, Size(s)) {
if(s[l] == ' ') { res.push_back(q); q = "";}
else { q += s[l]; }
}
return res;
}
string getLine() {
string s;
while(!feof(stdin)) {
char c = fgetc(stdin);
if(c <= 0) continue;
if(c == 13) continue;
if(c == 10) return s;
s += c;
}
return s;
}
int scanerr;
int getNum() {
#ifdef LINEBYLINE
string s = getLine();
return atoi(s.c_str());
#else
int i;
scanerr = scanf("%d", &i);
return i;
#endif
}
struct match {
string word;
int s0;
int s1;
};
int lcs[120000][256];
inline bool eq(const char *c1, const char *c2) {
if(*c2 == 0) return true;
if(*c1 != *c2) return false;
return eq(c1+1,c2+1);
}
void solveCase() {
int res = 0;
string t = getLine();
string p = getLine();
if(Size(t) > 100000) while(true) ;
if(Size(p) > 200) while(true) ;
vector<string> v = parsevs(p);
int gofrom = 0;
int N = Size(t);
vector<match> matches;
//printf("t [%s]\n", t.c_str());
//printf("p [%s]\n", p.c_str());
for(string s: v) if(s != "") {
for(char c: s) if(c < 'a' || c > 'z') while(1) true;
// printf("s [%s]\n", s.c_str());
bool fnd = false;
for(int i=gofrom; i<N; i++) {
if(eq(t.c_str()+i, s.c_str())) {
match m;
m.word = s;
m.s0 = i;
m.s1 = i + Size(s) - 1;
gofrom = i+1;
matches.push_back(m);
fnd = true;
break;
}
}
if(!fnd) break;
}
bool all = Size(matches) == Size(v);
printf("%s\n", all? "YES" : "NO");
if(Size(matches) == 0)
printf("0\n");
else {
bool fst = true;
for(auto m: matches) {
if(fst) fst=false; else printf(" ");
printf("%s %d %d", m.word.c_str(), m.s0, m.s1);
}
printf("\n");
}
if(!all) printf("0\n");
else {
int qty = 0;
for(int i=0; i<=Size(p); i++) lcs[0][i] = 0;
for(int i=0; i<=Size(t); i++) lcs[i][0] = 0;
for(int i=1; i<=Size(t); i++)
for(int j=1; j<=Size(p); j++) {
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
if(t[i-1] == p[j-1])
lcs[i][j] = max(lcs[i][j], lcs[i-1][j-1]+1);
}
if(0) for(int i=0; i<=Size(t); i++) {
printf("%c ", t[i]);
for(int j=0; j<=Size(p); j++)
printf("%d", lcs[i][j]);
printf("\n");
}
int m = lcs[Size(t)][Size(p)];
// printf("mchar = %d\n", mchar);
printf("%d\n", Size(p) + Size(t) - 2 * m);
}
}
#define P 1000000007
int main() {
if(!MANYTESTS) Tests = 1;
else Tests = getNum();
for(cnum=1; cnum<=Tests; cnum++)
solveCase();
// finish
return 0;
}
@jianminchen

This comment has been minimized.

Copy link
Owner Author

commented Sep 20, 2016

Code study - Learn from the best - C++ code
https://www.hackerrank.com/Eryxx

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.