Longest common subsequence問題を解くiPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
#include <algorithm>
#include <memory>
using namespace std;
#define MYMAX 1000
class LCSSolver {
public:
int solve(NSString*, NSString*);
private:
int sizeM;
int sizeN;
char m[MYMAX];
char n[MYMAX];
int dp[MYMAX][MYMAX];
int solve();
void notify(int, int, int);
};
int LCSSolver::solve(NSString *textM, NSString *textN) {
sizeM = (int)textM.length;
sizeN = (int)textN.length;
strcpy(m, &[textM UTF8String][0]);
strcpy(n, &[textN UTF8String][0]);
return solve();
};
int LCSSolver::solve() {
for (int i=0; i<sizeM; i++) {
for (int j=0; j<sizeN; j++) {
if (m[i] == n[j]) {
dp[i+1][j+1] = dp[i][j] + 1;
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
notify(i+1, j+1, dp[i+1][j+1]);
}
}
return dp[sizeM][sizeN];
};
void LCSSolver::notify(int i, int j, int v) {
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(i + j) * 0.1 * NSEC_PER_SEC), dispatch_get_main_queue(), ^{
[[NSNotificationCenter defaultCenter] postNotificationName:@”my message” object:@{@”i”:@(i), @”j”:@(j), @”v”:@(v)}];
});
}
@interface ViewController ()
@property (nonatomic, weak) UILabel *textA;
@property (nonatomic, weak) UILabel *textB;
@property (nonatomic) int result;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
UILabel *title = [[UILabel alloc] init];
title.text = @”Longest Common Subsequence”;
title.font = [UIFont boldSystemFontOfSize:25];
title.transform = CGAffineTransformMakeRotation(M_PI * 0.2);
[title sizeToFit];
title.textColor = [UIColor colorWithHue:0.75 saturation:0.2 brightness:1 alpha:1];
title.center = CGPointMake(CGRectGetMidX(self.view.bounds), 140);
[self.view addSubview:title];
UILabel *a = [[UILabel alloc] init];
a.font = [UIFont systemFontOfSize:15];
a.text = @”If you can dream it, you can do it”;
[a sizeToFit];
a.center = CGPointMake(CGRectGetMidX(self.view.bounds), 100);
[self.view addSubview:a];
UILabel *b = [[UILabel alloc] init];
b.font = [UIFont systemFontOfSize:15];
b.text = @”You never know what you can do till you try”;
b.numberOfLines = 0;
[b sizeToFit];
b.center = CGPointMake(CGRectGetMidX(self.view.bounds), 150);
[self.view addSubview:b];
self.textA = a;
self.textB = b;
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receive:) name:@”my message” object:nil];
}
– (void)receive:(NSNotification *)note {
int i = [note.object[@”i”] intValue];
int j = [note.object[@”j”] intValue];
NSString *v = [note.object[@”v”] stringValue];
float x = i * 13.5;
float y = j * 11 + 200;
UILabel *n = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 13.5, 11)];
n.backgroundColor = self.result == [v intValue]
? [UIColor colorWithHue:0.5 saturation:0.2 brightness:1 alpha:1]
: [UIColor colorWithHue:0.25 saturation:0.4 brightness:1 alpha:1];
n.text = v;
n.font = [UIFont systemFontOfSize:10];
[self.view addSubview:n];
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
shared_ptr<LCSSolver> cppClass(new LCSSolver());
self.result = cppClass->solve(
[self.textA.text stringByReplacingOccurrencesOfString:@” “ withString:@””],
[self.textB.text stringByReplacingOccurrencesOfString:@” “ withString:@””]);
}
@end