/* You are given two string. Find the Largest
Common Substring (not Subsequence).
First, insert all the suffix (suffix of "suffix" are "x",
"ix"......"suffix") of the first string in the "Trie",
then check with the all the second-string-suffix's.
*/
#include<bits/stdc++.h>
using namespace std;
int cnt=1, ans=0, st=0;
string s, ss;
struct node{
int next[26+1];
}ar[10000];
void new_trie(int cur){
for(int i=0; i<=26; i++)
ar[cur].next[i]=-1;
}
void insert(){ // Inserting the first string
int sz=s.size(), cur=0, x;
for(int i=0; i<sz; i++){
x=s[i]-'a';
if(ar[cur].next[x]==-1){
ar[cur].next[x]=cnt;
new_trie(cnt++);
}
cur=ar[cur].next[x];
}
}
void find(int stt){ // Checking with the second string
int sz=s.size(), cur=0, x, c=0;
for(int i=0; i<sz; i++){
x=s[i]-'a';
if(ar[cur].next[x]==-1)
break;
cur=ar[cur].next[x];
c++;
}
if(c>ans){ // when larger counter(c) is found
st=stt;
ans=c;
}
}
int main(){
int sz;
new_trie(0);
cin>>ss; // First String
sz=ss.size();
for(int i=1; i<=sz; i++){
s="";
for(int ii=sz-i; ii<sz; ii++)
s+=ss[ii];
insert();
}
cin>>ss; // Second String
sz=ss.size();
for(int i=1; i<=sz; i++){
s="";
for(int ii=sz-i; ii<sz; ii++)
s=s+ss[ii];
find(sz-i);
}
for(int i=st, cc=1; cc<=ans; i++, cc++)
cout<<ss[i];
return 0;
}
|
Showing posts with label Trie. Show all posts
Showing posts with label Trie. Show all posts
Thursday, October 19, 2017
Print Longest Common Substring
Friday, November 4, 2016
Solutoin of LightOJ 1224 - DNA Prefix
See the problem 1224 - DNA Prefix
/*
Bismillahir Rahmanir Rahim
Solution using "Trie"
*/
#include<bits/stdc++.h>
using namespace std;
long long k, i=0, x, cur, last, ss, sss, ans, mx;
string s;
struct node{
int next[4];
long long cnt;
}ar[2500109];
void new_trie(int cur){
ar[cur].next[0]=-1;
ar[cur].next[1]=-1;
ar[cur].next[2]=-1;
ar[cur].next[3]=-1;
ar[cur].cnt=1;
}
int insrt(){
ss=s.size(), cur=0;
for(k=0; k<ss; k++){
if(s[k]=='A') x=0;
else if(s[k]=='C')x=1;
else if(s[k]=='G')x=2;
else if(s[k]=='T')x=3;
if(ar[cur].next[x]==-1){
ar[cur].next[x]=last;
new_trie(last++);
cur=ar[cur].next[x];
}
else{
cur=ar[cur].next[x];
ar[cur].cnt++;
mx=(k+1)*ar[cur].cnt;
ans=max(mx, ans);
}
}
sss=max(ss, sss);
}
int main(){
long long t, n, cs=1;
cin>>t;
while(t--){
ans=0, mx=0, last=1, sss=0;
new_trie(0);
cin>>n;
while(n--){
cin>>s;
i++;
insrt();
}
cout<<"Case "<<cs++<<": "<<max(ans, sss)<<endl;
}
return 0;
}
|
Solution of LightOJ 1129 - Consistency Checker
View the problem 1129 - Consistency Checker
// Solution using "Trie"
#include<bits/stdc++.h>
using namespace std;
long long n, m, t, cs=1, i, j, last=1, xx, cur, k, x, fl;
string s;
struct trie{
bool endmark;
int next[11];
}r[100009];
void new_trie(int cur){
for(int zz=0; zz<10; zz++) r[cur].next[zz]=-1;
r[cur].endmark=false;
}
void insrt(){
cur=0, k=s.size();
for(int z=0; z<k; z++){
x=(int)s[z]-48;
if(r[cur].next[x]==-1){
r[cur].next[x]=last;
new_trie(last++);
cur=r[cur].next[x];
}
else{
cur=r[cur].next[x];
if(r[cur].endmark==true)fl=1;
if(z==k-1) fl=1;
}
if(fl==1)break;
}
r[cur].endmark=true;
}
int main(){
cin>>t;
while(t--){
cin>>n;
fl=0, last=1;
new_trie(0);
for(i=0; i<n; i++){
cin>>s;
insrt();
}
cout<<"Case "<<cs++<<": ";
if(fl==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
Thursday, November 3, 2016
Solution of POJ 2001-Shortest Prefixes
See the problem POJ 2001-Shortest Prefixes
// Solution using "Trie"
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<string>vt;
vector<string>::iterator it;
long long i, k, sz, cur, last, x;
string s;
struct node{
int next[26+1];
int cnt;
}ar[20109];
void new_trie(int cur){
for(int j=0; j<26; j++)ar[cur].next[j]=-1;
ar[cur].cnt=1;
}
void insrt(){
cur=0, sz=s.size();
for(i=0; i<sz; i++){
x=s[i]-'a';
if(ar[cur].next[x]==-1){
ar[cur].next[x]=last;
new_trie(last++);
cur=ar[cur].next[x];
}
else{
cur=ar[cur].next[x];
ar[cur].cnt++;
}
}
}
void fnd(){
sz=s.size(), cur=0;
for(i=0; i<sz; i++){
x=s[i]-'a';
cout<<s[i];
cur=ar[cur].next[x];
if(ar[cur].cnt==1) i=sz;
}
}
int main()
{
new_trie(0);
last=1;
while(getline(cin, s)){
if(s.size()==0) break;
vt.push_back(s);
insrt();
}
for(it=vt.begin(); it<vt.end(); it++){
s=*it;
cout<<s<<" ";
fnd();
cout<<endl;
}
return 0;
}
Monday, October 31, 2016
Solution of UVa 11488-Hyper Prefix Sets
See the problem UVa-11488
>>>This problem has been solved using "Trie". So if you don't known with "Trie", you should not try to understand this solution.<<<
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cur, last, ss, sss, ans, mx;
string s;
struct node{
int next[2];
long long cnt;
}ar[10000009];
void new_trie(int cur){
ar[cur].next[0]=-1;
ar[cur].next[1]=-1;
ar[cur].cnt=1;
}
int insrt(){
ss=s.size(), cur=0;
for(int k=0; k<ss; k++){
int x=(int)s[k]-48;
if(ar[cur].next[x]==-1){
ar[cur].next[x]=last;
new_trie(last++);
cur=ar[cur].next[x];
}
else{
cur=ar[cur].next[x];
ar[cur].cnt++;
mx=(k+1)*ar[cur].cnt;
ans=max(mx, ans);
}
}
sss=max(ss, sss);
}
int main(){
long long t, n;
cin>>t;
while(t--){
ans=0, mx=0, last=1, sss=0;
new_trie(0);
cin>>n;
while(n--){
cin>>s;
insrt();
}
cout<<max(ans, sss)<<endl;
}
return 0;
}
Solution of UVa 11362-Phone List
See the problem UVa-11362
#include<bits/stdc++.h>
using namespace std;
long long n, t, i, last=1, cur, k, x, fl;
string s;
struct node{
bool endmark;
int next[11];
}r[100009];
void new_trie(int cur){
for(int zz=0; zz<10; zz++){
r[cur].next[zz]=-1;
}
r[cur].endmark=false;
}
void insrt(){
cur=0, k=s.size();
for(int z=0; z<k; z++){
x=(int)s[z]-48;
if(r[cur].next[x]==-1){
r[cur].next[x]=last;
new_trie(last++);
cur=r[cur].next[x];
}
else{
cur=r[cur].next[x];
if(r[cur].endmark==true)fl=1;
if(z==k-1) fl=1;
}
if(fl==1) break;
}
r[cur].endmark=true;
}
int main(){
cin>>t;
while(t--){
cin>>n;
fl=0, last=1;
new_trie(0);
for(i=0; i<n; i++){
cin>>s;
insrt();
}
if(fl==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
|
Subscribe to:
Posts (Atom)