fork download
copy 
  1. #ifndef LOCAL
  2. #pragma GCC optimize ("-Ofast")
  3. #pragma GCC optimize ("-unroll-loops")
  4. #endif
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. //fast IO by yosupo
  10. struct Scanner {
  11.     FILE* fp = nullptr;
  12.     char line[(1 << 15) + 1];
  13.     size_t st = 0, ed = 0;
  14.     void reread() {
  15.         memmove(line, line + st, ed - st);
  16.         ed -= st;
  17.         st = 0;
  18.         ed += fread(line + ed, 1, (1 << 15) - ed, fp);
  19.         line[ed] = '\0';
  20.     }
  21.     bool succ() {
  22.         while (true) {
  23.             if (st == ed) {
  24.                 reread();
  25.                 if (st == ed) return false;
  26.             }
  27.             while (st != ed && isspace(line[st])) st++;
  28.             if (st != ed) break;
  29.         }
  30.         if (ed - st <= 50) reread();
  31.         return true;
  32.     }
  33.     template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  34.     bool read_single(T& ref) {
  35.         if (!succ()) return false;
  36.         while (true) {
  37.             size_t sz = 0;
  38.             while (st + sz < ed && !isspace(line[st + sz])) sz++;
  39.             ref.append(line + st, sz);
  40.             st += sz;
  41.             if (!sz || st != ed) break;
  42.             reread();            
  43.         }
  44.         return true;
  45.     }
  46.     template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  47.     bool read_single(T& ref) {
  48.         if (!succ()) return false;
  49.         bool neg = false;
  50.         if (line[st] == '-') {
  51.             neg = true;
  52.             st++;
  53.         }
  54.         ref = T(0);
  55.         while (isdigit(line[st])) {
  56.             ref = 10 * ref + (line[st++] - '0');
  57.         }
  58.         if (neg) ref = -ref;
  59.         return true;
  60.     }
  61.     template <class T> bool read_single(vector<T>& ref) {
  62.         for (auto& d : ref) {
  63.             if (!read_single(d)) return false;
  64.         }
  65.         return true;
  66.     }
  67.     void read() {}
  68.     template <class H, class... T> void read(H& h, T&... t) {
  69.         bool f = read_single(h);
  70.         assert(f);
  71.         read(t...);
  72.     }
  73.     Scanner(FILE* _fp) : fp(_fp) {}
  74. };
  75.  
  76. struct Printer {
  77.   public:
  78.     template <bool F = false> void write() {}
  79.     template <bool F = false, class H, class... T>
  80.     void write(const H& h, const T&... t) {
  81.         if (F) write_single(' ');
  82.         write_single(h);
  83.         write<true>(t...);
  84.     }
  85.     template <class... T> void writeln(const T&... t) {
  86.         write(t...);
  87.         write_single('\n');
  88.     }
  89.  
  90.     Printer(FILE* _fp) : fp(_fp) {}
  91.     ~Printer() { flush(); }
  92.  
  93.   private:
  94.     static constexpr size_t SIZE = 1 << 15;
  95.     FILE* fp;
  96.     char line[SIZE], small[50];
  97.     size_t pos = 0;
  98.     void flush() {
  99.         fwrite(line, 1, pos, fp);
  100.         pos = 0;
  101.     }
  102.     void write_single(const char& val) {
  103.         if (pos == SIZE) flush();
  104.         line[pos++] = val;
  105.     }
  106.     template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  107.     void write_single(T val) {
  108.         if (pos > (1 << 15) - 50) flush();
  109.         if (val == 0) {
  110.             write_single('0');
  111.             return;
  112.         }
  113.         if (val < 0) {
  114.             write_single('-');
  115.             val = -val;  // todo min
  116.         }
  117.         size_t len = 0;
  118.         while (val) {
  119.             small[len++] = char('0' + (val % 10));
  120.             val /= 10;
  121.         }
  122.         for (size_t i = 0; i < len; i++) {
  123.             line[pos + i] = small[len - 1 - i];
  124.         }
  125.         pos += len;
  126.     }
  127.     void write_single(const string& s) {
  128.         for (char c : s) write_single(c);
  129.     }
  130.     void write_single(const char* s) {
  131.         size_t len = strlen(s);
  132.         for (size_t i = 0; i < len; i++) write_single(s[i]);
  133.     }
  134.     template <class T> void write_single(const vector<T>& val) {
  135.         auto n = val.size();
  136.         for (size_t i = 0; i < n; i++) {
  137.             if (i) write_single(' ');
  138.             write_single(val[i]);
  139.         }
  140.     }
  141. };
  142.  
  143. Scanner sc(stdin);
  144. Printer pr(stdout);
  145.  
  146. using ll=long long;
  147. //#define int ll
  148.  
  149. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
  150. #define rep(i,b) rng(i,0,b)
  151. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
  152. #define per(i,b) gnr(i,0,b)
  153. #define pb push_back
  154. #define eb emplace_back
  155. #define a first
  156. #define b second
  157. #define bg begin()
  158. #define ed end()
  159. #define all(x) x.bg,x.ed
  160. #define si(x) int(x.size())
  161. #ifdef LOCAL
  162. #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
  163. #else
  164. #define dmp(x) void(0)
  165. #endif
  166.  
  167. template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
  168. template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
  169.  
  170. template<class t> using vc=vector<t>;
  171. template<class t> using vvc=vc<vc<t>>;
  172.  
  173. using pi=pair<int,int>;
  174. using vi=vc<int>;
  175.  
  176. template<class t,class u>
  177. ostream& operator<<(ostream& os,const pair<t,u>& p){
  178. 	return os<<"{"<<p.a<<","<<p.b<<"}";
  179. }
  180.  
  181. template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
  182. 	os<<"{";
  183. 	for(auto e:v)os<<e<<",";
  184. 	return os<<"}";
  185. }
  186.  
  187. #define mp make_pair
  188. #define mt make_tuple
  189. #define one(x) memset(x,-1,sizeof(x))
  190. #define zero(x) memset(x,0,sizeof(x))
  191. #ifdef LOCAL
  192. void dmpr(ostream&os){os<<endl;}
  193. template<class T,class... Args>
  194. void dmpr(ostream&os,const T&t,const Args&... args){
  195. 	os<<t<<" ";
  196. 	dmpr(os,args...);
  197. }
  198. #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
  199. #else
  200. #define dmp2(...) void(0)
  201. #endif
  202.  
  203. using uint=unsigned;
  204. using ull=unsigned long long;
  205.  
  206. template<class t,size_t n>
  207. ostream& operator<<(ostream&os,const array<t,n>&a){
  208. 	return os<<vc<t>(all(a));
  209. }
  210.  
  211. template<int i,class T>
  212. void print_tuple(ostream&,const T&){
  213. }
  214.  
  215. template<int i,class T,class H,class ...Args>
  216. void print_tuple(ostream&os,const T&t){
  217. 	if(i)os<<",";
  218. 	os<<get<i>(t);
  219. 	print_tuple<i+1,T,Args...>(os,t);
  220. }
  221.  
  222. template<class ...Args>
  223. ostream& operator<<(ostream&os,const tuple<Args...>&t){
  224. 	os<<"{";
  225. 	print_tuple<0,tuple<Args...>,Args...>(os,t);
  226. 	return os<<"}";
  227. }
  228.  
  229. template<class t>
  230. void print(t x,int suc=1){
  231. 	cout<<x;
  232. 	if(suc==1)
  233. 		cout<<"\n";
  234. 	if(suc==2)
  235. 		cout<<" ";
  236. }
  237.  
  238. ll read(){
  239. 	ll i;
  240. 	cin>>i;
  241. 	return i;
  242. }
  243.  
  244. vi readvi(int n,int off=0){
  245. 	vi v(n);
  246. 	rep(i,n)v[i]=read()+off;
  247. 	return v;
  248. }
  249.  
  250. pi readpi(int off=0){
  251. 	int a,b;cin>>a>>b;
  252. 	return pi(a+off,b+off);
  253. }
  254.  
  255. template<class t,class u>
  256. void print(const pair<t,u>&p,int suc=1){
  257. 	print(p.a,2);
  258. 	print(p.b,suc);
  259. }
  260.  
  261. template<class T>
  262. void print(const vector<T>&v,int suc=1){
  263. 	rep(i,v.size())
  264. 		print(v[i],i==int(v.size())-1?suc:2);
  265. }
  266.  
  267. string readString(){
  268. 	string s;
  269. 	cin>>s;
  270. 	return s;
  271. }
  272.  
  273. template<class T>
  274. T sq(const T& t){
  275. 	return t*t;
  276. }
  277.  
  278. void yes(){
  279. 	pr.writeln("YES");
  280. }
  281. void no(){
  282. 	pr.writeln("NO");
  283. }
  284. void possible(bool ex=true){
  285. 	#ifdef CAPITAL
  286. 	cout<<"POSSIBLE"<<"\n";
  287. 	#else
  288. 	cout<<"Possible"<<"\n";
  289. 	#endif
  290. 	if(ex)exit(0);
  291. 	#ifdef LOCAL
  292. 	cout.flush();
  293. 	#endif
  294. }
  295. void impossible(bool ex=true){
  296. 	#ifdef CAPITAL
  297. 	cout<<"IMPOSSIBLE"<<"\n";
  298. 	#else
  299. 	cout<<"Impossible"<<"\n";
  300. 	#endif
  301. 	if(ex)exit(0);
  302. 	#ifdef LOCAL
  303. 	cout.flush();
  304. 	#endif
  305. }
  306.  
  307. constexpr ll ten(int n){
  308. 	return n==0?1:ten(n-1)*10;
  309. }
  310.  
  311. const ll infLL=LLONG_MAX/3;
  312.  
  313. #ifdef int
  314. const int inf=infLL;
  315. #else
  316. const int inf=INT_MAX/2-100;
  317. #endif
  318.  
  319. int topbit(signed t){
  320. 	return t==0?-1:31-__builtin_clz(t);
  321. }
  322. int topbit(ll t){
  323. 	return t==0?-1:63-__builtin_clzll(t);
  324. }
  325. int botbit(signed a){
  326. 	return a==0?32:__builtin_ctz(a);
  327. }
  328. int botbit(ll a){
  329. 	return a==0?64:__builtin_ctzll(a);
  330. }
  331. int popcount(signed t){
  332. 	return __builtin_popcount(t);
  333. }
  334. int popcount(ll t){
  335. 	return __builtin_popcountll(t);
  336. }
  337. bool ispow2(int i){
  338. 	return i&&(i&-i)==i;
  339. }
  340. ll mask(int i){
  341. 	return (ll(1)<<i)-1;
  342. }
  343.  
  344. bool inc(int a,int b,int c){
  345. 	return a<=b&&b<=c;
  346. }
  347.  
  348. template<class t> void mkuni(vc<t>&v){
  349. 	sort(all(v));
  350. 	v.erase(unique(all(v)),v.ed);
  351. }
  352.  
  353. ll rand_int(ll l, ll r) { //[l, r]
  354. 	#ifdef LOCAL
  355. 	static mt19937_64 gen;
  356. 	#else
  357. 	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  358. 	#endif
  359. 	return uniform_int_distribution<ll>(l, r)(gen);
  360. }
  361.  
  362. template<class t>
  363. void myshuffle(vc<t>&a){
  364. 	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
  365. }
  366.  
  367. template<class t>
  368. int lwb(const vc<t>&v,const t&a){
  369. 	return lower_bound(all(v),a)-v.bg;
  370. }
  371.  
  372. vvc<int> readGraph(int n,int m){
  373. 	vvc<int> g(n);
  374. 	rep(i,m){
  375. 		int a,b;
  376. 		cin>>a>>b;
  377. 		//sc.read(a,b);
  378. 		a--;b--;
  379. 		g[a].pb(b);
  380. 		g[b].pb(a);
  381. 	}
  382. 	return g;
  383. }
  384.  
  385. vvc<int> readTree(int n){
  386. 	return readGraph(n,n-1);
  387. }
  388.  
  389. /*
  390.  * Time Complexity: Suffix Array: O(N + Character_Set_Size) time and space // 128 --- ASCII
  391.  *                  LCP: O(N) time and space
  392.  * Usage:
  393.  *       1. Suffix Array (returns s.size() elements, NOT considering 0-length/empty suffix)
  394.  *             auto sa = suffix_array(s); // s is the input string with ASCII characters
  395.  *             auto sa_wide_char = suffix_array(s, LIM); // LIM = max(s[i]) + 2, s is the string with arbitary big characters.
  396.  *       2. LCP:
  397.  *            auto lcp = LCP(s, suffix_array(s)); // returns s.size() elements, where lcp[i]=LCP(sa[i], sa[i+1])
  398.  * Status: Tested (DMOJ: ccc03s4, SPOJ: SARRAY (100pts), Yosupo's: Suffix Array & Number of Substrings, CodeForces EDU
  399.  */
  400.  
  401. // Based on: Rickypon, https://j...content-available-to-author-only...o.jp/submission/10105
  402. void induced_sort(const vector<int> &vec, int val_range, vector<int> &SA, const vector<bool> &sl, const vector<int> &lms_idx) {
  403.     vector<int> l(val_range, 0), r(val_range, 0);
  404.     for (int c : vec) {
  405.         if (c + 1 < val_range) ++l[c + 1];
  406.         ++r[c];
  407.     }
  408.     partial_sum(l.begin(), l.end(), l.begin());
  409.     partial_sum(r.begin(), r.end(), r.begin());
  410.     fill(SA.begin(), SA.end(), -1);
  411.     for (int i = lms_idx.size() - 1; i >= 0; --i)
  412.         SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
  413.     for (int i : SA)
  414.         if (i >= 1 && sl[i - 1]) {
  415.             SA[l[vec[i - 1]]++] = i - 1;
  416.         }
  417.     fill(r.begin(), r.end(), 0);
  418.     for (int c : vec)
  419.         ++r[c];
  420.     partial_sum(r.begin(), r.end(), r.begin());
  421.     for (int k = SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
  422.         if (i >= 1 && !sl[i - 1]) {
  423.             SA[--r[vec[i - 1]]] = i - 1;
  424.         }
  425. }
  426.  
  427. vector<int> SA_IS(const vector<int> &vec, int val_range) {
  428.     const int n = vec.size();
  429.     vector<int> SA(n), lms_idx;
  430.     vector<bool> sl(n);
  431.     sl[n - 1] = false;
  432.     for (int i = n - 2; i >= 0; --i) {
  433.         sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
  434.         if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
  435.     }
  436.     reverse(lms_idx.begin(), lms_idx.end());
  437.     induced_sort(vec, val_range, SA, sl, lms_idx);
  438.     vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
  439.     for (int i = 0, k = 0; i < n; ++i)
  440.         if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
  441.             new_lms_idx[k++] = SA[i];
  442.         }
  443.     int cur = 0;
  444.     SA[n - 1] = cur;
  445.     for (size_t k = 1; k < new_lms_idx.size(); ++k) {
  446.         int i = new_lms_idx[k - 1], j = new_lms_idx[k];
  447.         if (vec[i] != vec[j]) {
  448.             SA[j] = ++cur;
  449.             continue;
  450.         }
  451.         bool flag = false;
  452.         for (int a = i + 1, b = j + 1;; ++a, ++b) {
  453.             if (vec[a] != vec[b]) {
  454.                 flag = true;
  455.                 break;
  456.             }
  457.             if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
  458.                 flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
  459.                 break;
  460.             }
  461.         }
  462.         SA[j] = (flag ? ++cur : cur);
  463.     }
  464.     for (size_t i = 0; i < lms_idx.size(); ++i)
  465.         lms_vec[i] = SA[lms_idx[i]];
  466.     if (cur + 1 < (int)lms_idx.size()) {
  467.         auto lms_SA = SA_IS(lms_vec, cur + 1);
  468.         for (size_t i = 0; i < lms_idx.size(); ++i) {
  469.             new_lms_idx[i] = lms_idx[lms_SA[i]];
  470.         }
  471.     }
  472.     induced_sort(vec, val_range, SA, sl, new_lms_idx);
  473.     return SA;
  474. }
  475. vector<int> suffix_array(const string &s, const int LIM = 128) {
  476.     vector<int> vec(s.size() + 1);
  477.     copy(begin(s), end(s), begin(vec));
  478.     vec.back() = '$';
  479.     auto ret = SA_IS(vec, LIM);
  480.     ret.erase(ret.begin());
  481.     return ret;
  482. }
  483.  
  484. // Author: https://c...content-available-to-author-only...s.com/blog/entry/12796?#comment-175287
  485. // Uses kasai's algorithm linear in time and space
  486. vector<int> LCP(const string &s, const vector<int> &sa, const vector<int>& as) {
  487.     int n = s.size(), k = 0;
  488.     vector<int> lcp(n);
  489.     for (int i = 0; i < n; i++, k ? k-- : 0) {
  490.         if (as[i] == n - 1) {
  491.             k = 0;
  492.             continue;
  493.         }
  494.         int j = sa[as[i] + 1];
  495.         while (i + k < n && j + k < n && s[i + k] == s[j + k])
  496.             k++;
  497.         lcp[as[i]] = k;
  498.     }
  499.     lcp[n - 1] = 0;
  500.     return lcp;
  501. }
  502.  
  503. const int L=21;
  504. const int S=1<<L;
  505. int buf[L][S];
  506. void spinit(const vi&d){
  507. 	int n=d.size(),h=topbit(n);
  508. 	rep(i,n)buf[0][i]=d[i];
  509. 	rng(j,1,h+1){
  510. 		rep(i,n-(1<<j)+1)
  511. 			buf[j][i]=min(buf[j-1][i],buf[j-1][i+(1<<(j-1))]);
  512. 	}
  513. }
  514. int spget(int b,int e){
  515. 	assert(b<=e);
  516. 	if(b==e)return inf;
  517. 	int d=topbit(e-b);
  518. 	return min(buf[d][b],buf[d][e-(1<<d)]);
  519. }
  520.  
  521. const int kmax=1050;
  522. int dp[kmax][kmax],pre[kmax][kmax];
  523.  
  524. void slv(){
  525. 	int n,m,k;sc.read(n,m,k);
  526. 	string src;sc.read(src);
  527. 	string dst;sc.read(dst);
  528. 	int dif=abs(n-m),aff=k-dif;
  529. 	if(aff<0)return no();
  530. 	int lw=min(0,m-n)-aff/2,up=max(0,m-n)+aff/2;
  531. 	int s=up-lw+1;
  532. 	rep(i,k+1)rep(j,s){
  533. 		dp[i][j]=-inf;
  534. 		pre[i][j]=-inf;
  535. 	}
  536.  
  537. 	string rw=src+'W'+dst;
  538. 	vi sa=suffix_array(rw);
  539. 	vi as(n+m+1);rep(i,n+m+1)as[sa[i]]=i;
  540. 	vi lcp=LCP(rw,sa,as);
  541. 	//sparsetable<int,decltype(imin)> st(lcp,imin,inf);
  542. 	spinit(lcp);
  543. 	const auto common=[&](int i,int j){
  544. 		if(i==n||j==m)return 0;
  545. 		i=as[i];
  546. 		j=as[n+1+j];
  547. 		if(i>j)swap(i,j);
  548. 		return spget(i,j);
  549. 	};
  550.  
  551. 	dp[0][0-lw]=common(0,0)*2;
  552. 	rep(ans,k+1){
  553. 		if(dp[ans][m-n-lw]==n+m){
  554. 			yes();
  555. 			pr.writeln(ans);
  556. 			int idx=m-n;
  557. 			while(ans){
  558. 				int p=pre[ans][idx-lw];
  559. 				int i=(dp[ans-1][p-lw]-p)/2;
  560. 				int j=(dp[ans-1][p-lw]+p)/2;
  561. 				if(p==idx){
  562. 					pr.writeln("REPLACE",i+1,dst[j]);
  563. 				}else if(p+1==idx){
  564. 					pr.writeln("INSERT",i+1,dst[j]);
  565. 				}else if(p-1==idx){
  566. 					pr.writeln("DELETE",i+1);
  567. 				}else{
  568. 					assert(false);
  569. 				}
  570. 				ans--;
  571. 				idx=p;
  572. 			}
  573. 			return;
  574. 		}
  575. 		if(ans==k)return no();
  576. 		rng(idx,lw,up+1){
  577. 			if(dp[ans][idx-lw]>-inf){
  578. 				int i=(dp[ans][idx-lw]-idx)/2;
  579. 				int j=(dp[ans][idx-lw]+idx)/2;
  580. 				if(i<n&&j<m){
  581. 					int len=common(i+1,j+1);
  582. 					int y=i+1+len,x=j+1+len;
  583. 					int z=x+y;
  584. 					if(dp[ans+1][idx-lw]<z){
  585. 						dp[ans+1][idx-lw]=z;
  586. 						pre[ans+1][idx-lw]=idx;
  587. 					}
  588. 				}
  589. 				if(idx<up&&j<m){
  590. 					int len=common(i,j+1);
  591. 					int y=i+len,x=j+1+len;
  592. 					int z=x+y;
  593. 					if(dp[ans+1][idx+1-lw]<z){
  594. 						dp[ans+1][idx+1-lw]=z;
  595. 						pre[ans+1][idx+1-lw]=idx;
  596. 					}
  597. 				}
  598. 				if(lw<idx&&i<n){
  599. 					int len=common(i+1,j);
  600. 					int y=i+1+len,x=j+len;
  601. 					int z=x+y;
  602. 					if(dp[ans+1][idx-1-lw]<z){
  603. 						dp[ans+1][idx-1-lw]=z;
  604. 						pre[ans+1][idx-1-lw]=idx;
  605. 					}
  606. 				}
  607. 			}
  608. 		}
  609. 	}
  610. 	assert(false);
  611. }
  612.  
  613. signed main(){
  614. 	int t;sc.read(t);rep(_,t)
  615. 	slv();
  616. }
  617.  
Success #stdin #stdout 0s 4988KB
comments (?)
stdin
copy 
2
3 4 3
kot
plot
5 7 3
zycie
porazka
stdout
copy 
YES
2
INSERT 2 l
REPLACE 1 p
NO
https://ideone.com/XXIHgb
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!