fork download
copy 
  1. /*
  2.  *    J1K7_7
  3.  *
  4.  *    You can use my contents on a Creative Commons - Attribution 4.0 International - CC BY 4.0 License.  XD 
  5.  *    - JASKAMAL KAINTH
  6.  */
  7. #include <iostream>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <string>
  11. #include <vector>
  12. #include <deque>
  13. #include <queue>
  14. #include <stack>
  15. #include <set>
  16. #include <cstring>
  17. #include <cassert>
  18. #include <list>
  19. #include <map>
  20. #include <unordered_map>
  21. #include <iomanip>
  22. #include <algorithm>
  23. #include <functional>
  24. #include <utility>
  25. #include <bitset>
  26. #include <cmath>
  27. #include <cstdlib>
  28. #include <ctime>
  29. #include <cstdio>
  30. #include <limits>
  31. using namespace std;
  32. typedef long long          ll;
  33. typedef unsigned long long ull;
  34. typedef long double        ld;
  35. typedef pair<int,int>      pii;
  36. typedef pair<ll,ll>        pll;
  37. typedef vector<int>        vi;
  38. typedef vector<long long>  vll;
  39. #define left(x)		   (x << 1)
  40. #define right(x) 	   (x << 1) + 1
  41. #define mid(l, r) 	   ((l + r) >> 1)
  42. #define mp                 make_pair
  43. #define pb                 push_back
  44. #define all(a)             a.begin(),a.end()
  45. #define debug(x)	   {cerr <<#x<<" = " <<x<<"\n"; }
  46. #define debug2(x, y)       {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<"\n";}
  47. #define debug3(x, y, z)    {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  48. #define debug4(x, y, z, w) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<", "<<#w << " = " <<w <<"\n";}
  49. #define ss                 second
  50. #define ff                 first
  51. #define m0(x) 		   memset(x,0,sizeof(x))
  52.  
  53. inline int nextint(){ int x; scanf("%d",&x);   return x; }
  54. inline ll  nextll() { ll  x; scanf("%lld",&x); return x; }
  55.  
  56. #define gc getchar
  57. template <typename T> void scanint(T &x) {
  58. 	T c = gc(); while(((c < 48) || (c > 57)) && (c!='-')) c = gc();
  59. 	bool neg = false; if(c == '-') neg = true; x = 0; for(;c < 48 || c > 57;c=gc());
  60. 	for(;c > 47 && c < 58;c=gc())	x = (x*10) + (c - 48); if(neg)	x = -x;
  61. }
  62. // variadics
  63. template<typename T >T min_ ( T a , T b ) { return a > b ? b : a ; }
  64. template < typename T ,  typename... Ts > T min_( T first , Ts... last ){ return  min_(first, min_(last...)); }
  65.  
  66. // lambda exp auto  square = [](int inp) { return inp * inp; } ;
  67.  
  68. template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
  69. 	os<<"("<<t.first<<", "<<t.second<<")";
  70. 	return os;
  71. }
  72. template<typename T> ostream& operator<< (ostream& out, const vector<T>& v) {
  73.     out << "["; size_t last = v.size() - 1; for(size_t i = 0; i < v.size(); ++i) {
  74.     out << v[i]; if (i != last) out << ", "; } out << "]"; return out;
  75. }
  76.  
  77. ll pwr(ll base, ll p, ll mod){
  78. ll ans = 1; while(p) { if(p&1) ans=(ans*base)%mod; base=(base*base)%mod; p/=2; } return ans;
  79. }
  80. ll gcd(ll a, ll b) {  return b == 0 ? a : gcd(b,a%b); }
  81. ll lcm(ll a, ll b) {  return a*(b/gcd(a,b)); }
  82.  
  83. const long double PI = (long double)(3.1415926535897932384626433832795);
  84. const ll  mx_ll   = numeric_limits<ll> :: max();
  85. const int mx_int  = numeric_limits<int> :: max();
  86. const int mod = 1e9+7;
  87. const int oo = 0x3f3f3f3f;
  88. const ll  OO = 0x3f3f3f3f3f3f3f3fll;
  89.  
  90.  
  91. const int MAXN = 2e5+6;
  92.  
  93. struct SAAA
  94. {
  95. 	string s;
  96. 	int len;
  97. 	int iSA[MAXN], SA[MAXN];
  98. 	int cnt[MAXN], next_gen[MAXN], lcp[ MAXN ], LCP[MAXN][22]; //internal
  99. 	bool bh[MAXN], b2h[MAXN],m_arr[MAXN];
  100.  
  101. 	inline void init_SA()
  102. 	{
  103. 		for(int i = 0; i < MAXN; i++)
  104. 		{
  105. 			iSA[i] = SA[i] = cnt[i] = next_gen[i] = lcp[i] = 0;
  106. 			bh[i] = b2h[i] = m_arr[i] = 0;
  107. 			for(int j = 0; j < 22; j++)
  108. 				LCP[i][j] = 0;
  109. 		}
  110. 	}
  111.  
  112. 	bool smaller_first_char(int a, int b){
  113. 		return s[a] < s[b];
  114. 	}
  115.  
  116. 	void SuffixSort(int n) {
  117. 		for (int i=0; i<n; ++i){
  118. 			SA[i] = i;
  119. 		}
  120. 		vector<pair<char,int> >arrr;
  121. 		for(int i = 0; i < n; i++)
  122. 		{
  123. 			arrr.pb({s[SA[i]],SA[i]});  
  124. 		}
  125. 		sort(all(arrr));
  126. 		for(int i = 0; i < n; i++)
  127. 		{
  128. 			SA[i] = arrr[i].ss; 
  129. 		}
  130. 		for (int i=0; i<n; ++i){
  131. 			bh[i] = i == 0 || s[SA[i]] != s[SA[i-1]];
  132. 			b2h[i] = false;
  133. 		}
  134. 		for (int h = 1; h < n; h <<= 1){
  135. 			int buckets = 0;
  136. 			for (int i=0, j; i < n; i = j){
  137. 				j = i + 1;
  138. 				while (j < n && !bh[j]) j++;
  139. 				next_gen[i] = j;
  140. 				buckets++;
  141. 			}
  142. 			if (buckets == n) break;
  143. 			for (int i = 0; i < n; i = next_gen[i]){
  144. 				cnt[i] = 0;
  145. 				for (int j = i; j < next_gen[i]; ++j){
  146. 				iSA[SA[j]] = i;
  147. 			}
  148. 		}
  149. 		cnt[iSA[n - h]]++;
  150. 		b2h[iSA[n - h]] = true;
  151. 		for (int i = 0; i < n; i = next_gen[i]){
  152. 			for (int j = i; j < next_gen[i]; ++j){
  153. 				int s = SA[j] - h;
  154. 				if (s >= 0){
  155. 					int head = iSA[s];
  156. 					iSA[s] = head + cnt[head]++;
  157. 					b2h[iSA[s]] = true;
  158. 				}
  159. 			}
  160. 			for (int j = i; j < next_gen[i]; ++j){
  161. 				int s = SA[j] - h;
  162. 				if (s >= 0 && b2h[iSA[s]]){
  163. 					for (int k = iSA[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
  164. 				}
  165. 			}
  166. 		}
  167. 		for (int i=0; i<n; ++i){
  168. 			SA[iSA[i]] = i;
  169. 			bh[i] |= b2h[i];
  170. 		}
  171. 		}
  172. 		for (int i=0; i<n; ++i){
  173. 			iSA[SA[i]] = i;
  174. 		}
  175. 	}
  176.  
  177. 	void InitLCP(int n) {
  178. 		for (int i=0; i<n; ++i) 
  179. 			iSA[SA[i]] = i;
  180. 		lcp[0] = 0;
  181. 		for (int i=0, h=0; i<n; ++i) {
  182. 			if (iSA[i] > 0) {
  183. 				int j = SA[iSA[i]-1];
  184. 				while (i + h < n && j + h < n && s[i+h] == s[j+h]) 
  185. 					h++;
  186. 				lcp[iSA[i]] = h;
  187. 				if (h > 0) 
  188. 					h--;
  189. 			}
  190. 		}
  191. 	}
  192.  
  193. 	void ConstructLCP() {
  194. 		InitLCP( len );
  195. 		for(int i = 0;i<len;++i)
  196. 			LCP[i][0] = lcp[i];
  197. 		for(int j = 1;(1<<j)<=len;++j){
  198. 			for(int i = 0;i+(1<<j)-1<len;++i){
  199. 				if(LCP[i][j-1]<=LCP[i+ ( 1<<(j-1) )][j-1])
  200. 					LCP[i][j] = LCP[i][j-1];
  201. 				else
  202. 					LCP[i][j] = LCP[i+(1<<(j-1))][j-1];
  203. 			}
  204. 		}
  205. 	}
  206.  
  207. 	int GetLCP(int x, int y) {
  208. 		if(x == y) return len-SA[x];
  209. 		if(x > y) swap(x,y);
  210. 		int log = 0;
  211. 		while((1<<log)<=(y-x)) ++log;
  212. 		--log;
  213. 		return min(LCP[x+1][log],LCP[y-(1<<log)+1][log]);
  214. 	}
  215. }str[2];
  216. int main()
  217. {
  218.     ios_base::sync_with_stdio(false); cin.tie(0);
  219. 	string s1, s2; 
  220. 	cin >> s1 >> s2;
  221.  
  222. 	string st = s1 + "$" + s2;
  223.  
  224. 	str[0].s = st;
  225. 	str[0].len = st.length();
  226. 	str[0].init_SA();
  227. 	str[0].SuffixSort(st.length());
  228. 	str[0].ConstructLCP();
  229.  
  230. 	string c1 = s1;
  231. 	reverse(all(c1));
  232. 	string c2 = s2;
  233. 	reverse(all(c2));
  234. 	string ts = c1 + "$" + c2;
  235.  
  236. 	str[1].s = ts;
  237. 	str[1].len = ts.length();
  238. 	str[1].init_SA();
  239. 	str[1].SuffixSort(ts.length());
  240. 	str[1].ConstructLCP();
  241.  
  242. 	int lens = s1.length();
  243. 	int lent = s2.length();
  244.  
  245. 	int q; cin >> q;
  246. 	while(q--)
  247. 	{
  248. 		int k , a, b , c, d;
  249. 		cin >> k >> a >> b >> c >> d;
  250. 		a--,c--,b--,d--;
  251. 		if((b-a) != (d-c))
  252. 		{
  253. 			cout << "NO\n";
  254. 			continue;
  255. 		}
  256. 		int flag = 0;
  257. 		for(int ik = 0; ik <= k; ik++)
  258. 		{
  259. 			if(ik == 0)
  260. 			{
  261. 				int lcp1 = str[0].GetLCP(str[0].iSA[a],str[0].iSA[c+lens+1]);
  262. 				lcp1 = min(lcp1,b-a+1);
  263. 				if(lcp1 == (b-a+1))
  264. 				{
  265. 					flag = 1;  
  266. 					break;
  267. 				}
  268. 			}
  269. 			if(ik == 1)
  270. 			{
  271. 				int na = lens - a - 1;
  272. 				int nb = lens - b - 1;
  273. 				int nc = lent - c - 1;
  274. 				int nd = lent - d - 1;
  275.  
  276. 				int lcp1 = str[0].GetLCP(str[0].iSA[a],str[0].iSA[c + lens + 1]);
  277. 				lcp1 = min(lcp1,b-a+1);
  278.  
  279. 				int lcp2 = str[1].GetLCP(str[1].iSA[nb],str[1].iSA[nd + lens + 1]);
  280. 				lcp2 = min(lcp2,d-c+1);
  281.  
  282. 				int crap = b-a-lcp1-lcp2+1;
  283. 				if(crap <= 1)
  284. 				{
  285. 					flag = 0;
  286. 					break;
  287. 				}
  288. 				if(crap == 2)
  289. 				{
  290. 					if((s1[a+lcp1] == s2[lcp1+c+1]) && (s1[a+lcp1+1] == s2[lcp1+c]))
  291. 					{
  292. 						flag = 1;  
  293. 					}
  294. 					break;
  295. 				}
  296. 			}
  297. 			if(ik == 2)
  298. 			{
  299. 				int na = lens - a - 1;
  300. 				int nb = lens - b - 1;
  301. 				int nc = lent - c - 1;
  302. 				int nd = lent - d - 1;
  303.  
  304. 				int lcp1 = str[0].GetLCP(str[0].iSA[a],str[0].iSA[c + lens + 1]);
  305.  
  306. 				int lcp2 = str[1].GetLCP(str[1].iSA[nb],str[1].iSA[nd + lens + 1]);
  307.  
  308.  
  309. 				char x,y,z;
  310. 				x = st[a+lcp1];
  311. 				y = st[a+lcp1+1];
  312. 				z = st[a+lcp1+2];
  313.  
  314. 				char x2,y2,z2;
  315. 				x2 = st[lens+c+lcp1+1];
  316. 				y2 = st[lens+c+lcp1+2];
  317. 				z2 = st[lens+c+lcp1+3];
  318.  
  319.  
  320. 				if((lcp1+lcp2+3) == (b-a+1))
  321. 				{
  322. 					if((x2 == y && y2 == z && z2 == x) || (x2 == z && y2 == x && z2 == y))
  323. 					{
  324. 						flag = 1;  
  325. 					}
  326. 					break;
  327. 				}
  328. 				int lcp3 = str[0].GetLCP(str[0].iSA[a+lcp1+2],str[0].iSA[lens + c + lcp1 + 3]);
  329.  
  330. 				int tem = lcp1 + lcp2 + lcp3 + 3 ;
  331. 				if(tem == (b-a))
  332. 				{
  333. 					if((s1[a+lcp1] == s2[c+lcp1+1]) && (s1[a+lcp1+1] == s2[c+lcp1]))
  334. 					{
  335. 						if((s1[a+2+lcp1+lcp3] == s2[c+lcp1+lcp3+3]) && (s1[a+lcp1+3+lcp3] == s2[c+lcp1+lcp3+2]))
  336. 						{
  337. 							flag = 1;
  338. 							break;
  339. 						}
  340. 					}
  341. 				}
  342. 				else
  343. 				{
  344. 					flag = 0;
  345. 					break;
  346. 				}
  347. 			}
  348. 		}
  349. 		if(flag)
  350. 		{
  351. 			cout << "YES\n";
  352. 		}
  353. 		else
  354. 		{
  355. 			cout << "NO\n";
  356. 		}
  357. 	}
  358.     return 0;
  359. }
  360.  
  361.  
Success #stdin #stdout 0s 46840KB
comments (?)
stdin
copy 
babba
abbaa
3
1 2 3 3 4
1 2 4 2 4
2 2 4 2 4
stdout
copy 
YES
NO
YES
https://ideone.com/HHmJ31
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!