Ignacio Morales
BAN USERYou could modify the rabin karp algorithm to do that. I will write the code for tonight and post it. :) Have a nice day!
- Ignacio Morales November 25, 2013- (NSMutableString *) removeDuplicates:(NSString *) string
if(string && [string length] > 1){
NSMutableString *stringMutable = [string mutableCopy];
CFMutableBitVectorRef charExists = CFBitVectorCreateMutable(kCFAllocatorDefault,0);
unsigned int index = 0;
while( index < [stringMutable length])
{
if(CFBitVectorGetBitAtIndex(charExists,[stringMutable characterAtIndex:index]) == 0){
CFBitVectorFlipBitAtIndex(charExists,[stringMutable characterAtIndex:index]);
index++;
} else {
[stringMutable deleteCharactersInRange:NSMakeRange(index,1)];
}
}
NSLog(@"%@",stringMutable);
} else {
return string;
NSLog(@"Nothing to be done here");
}
}
A solution with a stack in Objective C
/* Stack */
@interface Stack : NSObject{
NSMutableArray* stack;
}
-(void)push:(id)item;
-(id)pop;
-(id)peek;
-(int)count;
@property(nonatomic,readonly) int count;
@end
/* Node */
@interface Node : NSObject{
int value;
Node* left;
Node* right
}
@property unsigned int value;
@property (nonatomic,strong) Node *left;
@property (nonatomic,strong) Node *right;
@end
- (bool) areEqual:(Node *) rootA and:(Node *)rootB
{
[stack push:rootA];
[stack push:rootB];
while([stack count] != 0){
Node *tempA = (Node *)[stack pop];
Node *tempB = (Node *)[stack pop];
//Right
if(([[tempA right] class] == [[tempB right] class]) ){
if([tempA right] != nil){
[stack push:[tempA right]];
[stack push:[tempB right]];
}
} else {
return false;
}
//Left
if(([[tempA left] class] == [[tempB left] class]) ){
if([tempA left] != nil){
[stack push:[tempA left]];
[stack push:[tempB left]];
}
} else {
return false;
}
}
return true;
}
I ended up using Knuth-robin-pratt. I imported the book Clarissa, or, the History of a Young Lady by Samuel Richardson. My first approach was to find all the index of chars in which an occurrence of the word happened. The I remembered you want the first smallest substring in which it occurs.
it is a bit complex but I really do hope it helps! oh and complexity is O(n+m) where n is the size of the word and m is the size of the document.
- Ignacio Morales November 25, 2013