Code: Select all
function getHash (const s: str16): longint;
begin
getHash := 0;
tt := 1; //1, 26, 26^2, 26^3, ..., 26^16
for tti:=1 to length(s) do //all the length
begin
getHash := (getHash + (tt * (ord(s[tti])-ord('a')+1)) mod MAXHASH) mod MAXHASH; //26^n * ordinal_of_the_character
tt := (tt * 26) mod MAXHASH; // 26^n => 26^(n+1)
end
end;
Code: Select all
procedure insList (const s: str16; const i:integer);
begin
tt := getHash (s);
tt2 := new (prec);
(tt2^).ind := i;
(tt2^).next:= hashMap[tt];
hashMap[tt] := tt2;
end;
Code: Select all
function getInd (const s: str16): longint;
var
t: prec;
begin
tt := getHash (s); //keep hash in 'tt'
if hashMap[tt] = nil then //if list with index 'tt' is empty, then word is not in the dictionary
begin
getInd := -1;
exit;
end;
t := hashMap[tt];
while t<>nil do //iterate through all the nodes in the linked list and compare them with given word..
begin
if a[(t^).ind] = s then
begin
getInd := (t^).ind;
exit;
end;
t := (t^).next;
end;
getInd := -1;
end;
Code: Select all
{$R-}{$S-}{$Q-}{$B-}
program uva10029Solution;
type
str16 = string[16];
const
MAXHASH = 999979; //prime number
type
prec = ^rec;
rec = record
ind: integer;
next: prec;
end;
var
a: array [0..25000] of str16;
b: array [0..25000] of longint;
hashmap: array [0..MAXHASH] of prec;
s,s1,t,t1: str16;
i,j,k,l,m,n: longint;
ans: longint;
ch,tc: char;
left,right,middle,wm: longint;
maxval,maxind: longint;
tt,tti: longint;
tt2: prec;
function getHash (const s: str16): longint;
begin
getHash := 0;
tt := 1;
for tti:=1 to length(s) do
begin
getHash := (getHash + (tt * (ord(s[tti])-ord('a')+1)) mod MAXHASH) mod MAXHASH;
tt := (tt * 26) mod MAXHASH;
end
end;
function getInd (const s: str16): longint;
var
t: prec;
begin
tt := getHash (s);
if hashMap[tt] = nil then
begin
getInd := -1;
exit;
end;
t := hashMap[tt];
while t<>nil do
begin
if a[(t^).ind] = s then
begin
getInd := (t^).ind;
exit;
end;
t := (t^).next;
end;
getInd := -1;
end;
procedure insList (const s: str16; const i:integer);
begin
tt := getHash (s);
tt2 := new (prec);
(tt2^).ind := i;
(tt2^).next:= hashMap[tt];
hashMap[tt] := tt2;
end;
begin
ans := 0;
for i:=0 to MAXHASH do
hashMap[i] := nil;
while not eof do
begin
readln (s);
l := length(s);
inc (n);
a[n] := s;
insList(a[n],n);
if n=1 then
begin
ans := 1;
b[1] := 1;
continue;
end;
maxval := 0;
//transformations
// 1) change
t := s;
for i:=1 to l do
begin
tc := t[i];
for ch:='a' to 'z' do
begin
if ch=tc then continue;
t[i] := ch;
if (t>s) then break;
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
t[i] := tc;
end;
// 2) remove
for i:=1 to l do
begin
t := s;
delete (t,i,1);
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
// 3) add
for i:=1 to l+1 do
begin
t := s;
insert('#',t,i);
for ch:='a' to 'z' do
begin
t[i] := ch;
if t>s then break;
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
end;
if maxval = 0 then
b[n] := 1
else
begin
b[n] := maxval + 1;
if b[n]>ans then
ans := b[n];
end;
end;
for i:=0 to MAXHASH do
begin
while hashMap[i]<>nil do
begin
tt2 := (hashMap[i]^).next;
dispose(hashMap[i]);
hashMap[i] := tt2;
end;
end;
writeln (ans);
end.
Code: Select all
function getInd (const s: str16): longint;Code: Select all
#define HDIV 533879
int lookup(const char *s, int add = -1) {
int hash = 0;
for (int i = 0; s[i]; i++) {
hash = hash * 31 + s[i] - 'a';
if (hash >= HDIV) hash %= HDIV;
}
...
Yesandysoft wrote:HDIV is your hash map size, right?
Character arrays are faster.by the way, should I use STL string or just character arrays if I decide to write in C++?
Code: Select all
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <vector>
#define max 26000
using namespace std;
int dp[max];
vector<string> v;
vector<int> adj[max];
int bin_search(string s,int low,int high)
{
if(low>high)
return 0;
int mid=(low+high)/2;
if(v[mid]==s)
return mid;
if(v[mid]>s)
return bin_search(s,low,mid-1);
else
return bin_search(s,mid+1,high);
}
int get_logest_ladder(int u)
{
int maxim=0;
if(dp[u]!=-1)
return dp[u];
for(int i=0;i<adj[u].size();i++)
{
int v=adj[u][i];
dp[v]=get_logest_ladder(v);
int k=1+dp[v];
if(k>maxim)
maxim=k;
}
dp[u]=maxim;
return dp[u];
}
int main(int argc, char const *argv[])
{
string s;
while(cin>>s)
{
v.push_back(s);
}
for(int i=0;i<v.size();i++)
{
string s1=v[i];
for(int j=0;j<s1.length();j++)
{
for(char ch='a';ch<='z';ch++)
{
string s2=s1;
s2.at(j)=ch;
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
for(int j=0;j<=s1.length();j++)
{
for(char ch='a';ch<='z';ch++)
{
string s2=s1;
s2.insert(s2.begin()+j,ch);
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
for(int j=0;j<s1.length();j++)
{
string s2=s1;
s2.erase(s2.begin()+j);
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
memset(dp,-1,sizeof(dp));
int maxim=0;
for(int i=0;i<v.size();i++)
{
int k=get_logest_ladder(i);
if(k>maxim)
maxim=k;
}
cout<<maxim+1<<"\n";
return 0;
}