Apr 17, 2014 at 12:50am UTC
I want my code to perform O(N), where N is the length of the longer string.
Can you help me out?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
#include <iostream>
#include <string>
#include <vector>
using std::string;
using std::vector;
using std::cout;
using std::endl;
bool ed1(const std::string& s1, const std::string& s2)
{
size_t s1length = s1.length(); // length of s1
size_t s2length = s2.length(); // length of s2
if (s1length < s2length){ // For the case s2 is longer than s1
return ed1(s2, s1);
}
vector<int > ins(s2length + 1);
vector<int > del(s2length + 1);
vector<int > sub(s2length + 1);
vector<int > p(s2length + 1);
vector<int > q(s2length + 1);
vector<int > r;
vector<int > s(s1length);
vector<int >::iterator pos;
p.at(0) = 0;
/*for (size_t i = 1; i <= s2length; i++)
p.at(i) = p.at(i - 1) + 1;
*/
for (pos = p.begin()+1; pos != p.end(); pos++){
*pos = *(pos-1) + 1;
}
for (size_t i = 1; i <= s1length; i++)
{
q.at(0) = p.at(0) + 1;
for (size_t k = 1; k <= s2length; k++)
{
int d_del = p.at(k) + 1;
int d_ins = q.at(k - 1) + 1;
int d_sub = p.at(k - 1) + (s1.at(i - 1) == s2.at(k - 1) ? 0 : 1);
q.at(k) = fmin(fmin(d_del, d_ins), d_sub); // Just for the edit distance.
del.at(k) = d_del; // To find if any character is deleted.
ins.at(k) = d_ins; // To find if any character is inserted.
sub.at(k) = d_sub; // To find if any character is changed.
//cout <<"k = "<<k<<" d_del = "<<d_del << " d_ins = " <<d_ins << " d_sub = " << d_sub << endl;
}
r = p;
p = q;
q = r;
}
//cout << "p[s2length] = " << p[s2length] << " del[s2length] = " << del[s2length] << " ins[s2length] = " << ins[s2length] << " sub[s2length] = " << sub[s2length] << endl;
int result = p[s2length]; // result of the edit distance.
if (result <= 1 || ((del[s2length] == 2 || sub[s2length] == 2) && result == 2)){ // Return true if the edit distance is less than one, or the edit distance is 1.5.
return true ;
}
else {
return false ;
}
/*
p.at(0) = 0;
for (size_t i = 1; i <= s2length; i++)
p.at(i) = p.at(i - 1) + 1;
for (size_t i = 1; i <= s1length; i++)
{
q.at(0) = p.at(0) + 1;
for (size_t k = 1; k <= s2length; k++)
{
int d_del = p.at(k) + 1;
int d_ins = q.at(k - 1) + 1;
int d_sub = p.at(k - 1) + (s1.at(i - 1) == s2.at(k - 1) ? 0 : 1);
q.at(k) = fmin(fmin(d_del, d_ins), d_sub); // Just for the edit distance.
del.at(k) = d_del;
ins.at(k) = d_ins;
sub.at(k) = d_sub;
//cout <<"k = "<<k<<" d_del = "<<d_del << " d_ins = " <<d_ins << " d_sub = " << d_sub << endl;
}
r = p;
p = q;
q = r;
}
cout << "p[s2length] = " << p[s2length] << " del[s2length] = " << del[s2length] << " ins[s2length] = " << ins[s2length] << " sub[s2length] = " << sub[s2length] << endl;
int result = p[s2length];
if (result <= 1 || ((del[s2length] == 2 || sub[s2length] ==2)&&result ==2)){
return true;
}
else{
return false;
}
*/
}
int main(){
if (ed1("exist" , "list" )){
cout << "true" << endl;
}
else {
cout << "false" << endl;
}
}
Last edited on Apr 17, 2014 at 2:37am UTC
Apr 17, 2014 at 1:45am UTC
What in the world is this code even meant to do?
Apr 17, 2014 at 1:47am UTC
This method is for finding the edit distance of two strings.
Apr 17, 2014 at 2:12am UTC
where is using namespace you have four errors
Apr 17, 2014 at 2:21am UTC
You don't need using namespace xxxxx;
and you should generally avoid it as that defeats the purpose of avoiding naming collisions. He has a better way by only including the specific ones used which is fine.
Though I agree with Lachlan you should tell us what it does. Examples: Remove the unnecessary code (the random commented out stuff). Then provide useful comments and tell us more information on what you are trying to do.
Apr 17, 2014 at 2:36am UTC
This is a method to find the edit distance of two strings.
Also, I wanted to make it perform O(N), but I couldn't find out how...
Last edited on Apr 17, 2014 at 2:37am UTC
Apr 17, 2014 at 2:37am UTC
I changed the code to make you guys easier to understand.
Apr 17, 2014 at 3:23am UTC
> This method is for finding the edit distance of two strings.
> bool ed1(const std::string& s1, const std::string& s2)
...
¿what part of `Remove the unnecessary code' did you not understand?
Apr 17, 2014 at 3:24am UTC
what part of `I couldn't find out how' did you not understand?
Apr 17, 2014 at 3:29am UTC
you couldn't find a O(N) algorithm, (¿time or space?)
¿what does line 57 have to do with that?
¿what's the difference between 68-103 and 31-67?
¿why do I need to bother with 68-103?
Last edited on Apr 17, 2014 at 3:30am UTC
Apr 17, 2014 at 3:32am UTC
You don't need to bother with 68-103.
All you need is 1-67.
Apr 17, 2014 at 3:33am UTC
line 57 was written to check if the method was working properly
Apr 17, 2014 at 3:48am UTC
> You don't need to bother with 68-103.
then don't post it.
So, looking at the return type of your function, it should be obvious that you are not really interest in calculating the edit distance, but to know if such distance is 1 or 1.5 (¿?)
Considering the recursive approach, once that you have surpassed the maximum distance you could stop and return infinity.
Apr 17, 2014 at 3:56am UTC
if you are not busy, would you show me how to do so?
Apr 17, 2014 at 5:04pm UTC
how can I use 'last' or a(0:size-1)?
Apr 17, 2014 at 5:07pm UTC
Can you make this code runnable? Because, I'm a beginner of c++ yet...