paste bin
Author
Language
C++
Plain text
Accesslog
Action script
Ada
Apache
Arduino
Armasm
Autohotkey
Awk
Bash
Basic
Brainfuck
C
Clojure
Cmake
C#
css
D
Delphi
Dockerfile
Erlang
Fortran
F#
Gauss
Go
Gradle
Graphql
Groovy
Haskell
Ini
Java
JavaScript
json
Julia
Kotlin
Lasso
LaTeX
Leaf
lisp
llvm
Lua
Makefile
Markdown
Mathematica
Matlab
Nginx
Objective-C
Ocaml
Oxygene
Perl
PgSQL
php
Powershell
Processing
Profile
Properties
Puppet
Purebasic
Python
Q
QML
R
Ruby
Rust
Scala
Scheme
Scilab
Shell
Smalltalk
SQL
Swift
Typescript
VB.NET
VB Script
Verilog
Vim
Wasm
x86asm
Xml
Xquery
Yaml
source code:
#include <cstdio> #include <cstring> #include <algorithm> using std::max; int LCS(char* s1, char* s2,char *res) { int i,j,M,N,k=0,upbd; M=strlen(s1); N=strlen(s2); int **dp; dp=new int* [M+2]; for(i=0;i<M+2;i++) dp[i]=new int [N+2]; for(i=0;i<N+2;i++) dp[0][i]=0; for(i=1;i<M+1;i++) { dp[i][0]=0; for(j=1;j<N+1;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } k=dp[M][N]; i=M; j=N; upbd=k; res[k]='\0'; while(i>0 && j>0) { if(dp[i-1][j]==dp[i-1][j-1] && dp[i-1][j-1]==dp[i][j-1] ) { if (dp[i][j]==dp[i-1][j-1]+1) res[--upbd]=s1[i-1]; i--; j--; } else { if(dp[i-1][j]==dp[i][j]) i--; else j--; } } for(i=0;i<M+2;i++) delete [] dp[i]; delete [] dp; return k; } void solve(char *s) { char *s1,*s2,*res,*target; int N=strlen(s),i,d,maxVal=-1; s1=new char [N+1]; s2=new char [N+1]; res=new char [N+1]; target=new char [N+1]; for(i=1;i<N;i++) { strcpy(s1,s); s1[i]=0; strcpy(s2,s+i); d=LCS(s1,s2,res); if(d>maxVal) { maxVal=d; strcpy(target,res); } } printf("%s\n",target); delete [] s1; delete [] s2; delete [] res; delete [] target; } #define MAXLENGTH 303 int main(void) { char s[MAXLENGTH]; while(scanf("%s",s)!=EOF) { if(strcmp("#END",s)==0) break; solve(s); } return 0; }
comment: