This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../string/longestcommonsubstring.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int q; cin>>q; while(q--){ string s,t; cin>>s>>t; cout<<longest_common_substring(s,t).size()<<'\n'; } return 0; }
#line 1 "test/aoj/ALDS1_10_C.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "string/longestcommonsubstring.cpp" #line 3 "string/longestcommonsubstring.cpp" using namespace std; #endif //BEGIN CUT HERE // O(nm) string longest_common_substring(string s,string t){ int n=s.size(),m=t.size(); s+='$';t+='%'; vector< vector<int> > dp(n+2,vector<int>(m+2,-(n+m))); dp[0][0]=0; auto chmax=[&](int &a,int b){if(a<b) a=b;}; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ chmax(dp[i+1][j],dp[i][j]); chmax(dp[i][j+1],dp[i][j]); chmax(dp[i+1][j+1],dp[i][j]+(s[i]==t[j])); } } if(dp[n][m]==0) return ""s; string ans; int i=n,j=m; while(dp[i][j]){ if((dp[i][j]==dp[i-1][j-1]+1) and (s[i-1]==t[j-1])){ ans+=s[i-1]; i--;j--; }else if(dp[i][j]==dp[i-1][j]) i--; else j--; } reverse(ans.begin(),ans.end()); return ans; } //END CUT HERE //INSERT ABOVE HERE #ifndef call_from_test signed DP_F(){ string s,t; cin>>s>>t; cout<<longest_common_substring(s,t)<<endl; return 0; } /* verified on 2020/12/21 https://atcoder.jp/contests/dp/tasks/dp_f */ signed main(){ DP_F(); return 0; } #endif #line 8 "test/aoj/ALDS1_10_C.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int q; cin>>q; while(q--){ string s,t; cin>>s>>t; cout<<longest_common_substring(s,t).size()<<'\n'; } return 0; }