import java.util.regex.Pattern;
class Test {
private Pattern pattern;
private boolean[] table;
public boolean matches1
(String a
) { return pattern.matcher(a).matches();
}
public boolean matches2
(String a
) { int length = a.length();
for (int i = 0; i < length; ++i)
if (!this.table[a.charAt(i)]) return false;
return true;
}
public Test() {
String chars
= "adhst32pomnbqf51kczyx94"; this.
pattern = Pattern.
compile(String.
format("[%s]*", chars
)); this.table = new boolean[256];
for (int i = 0; i < chars.length(); ++i)
this.table[chars.charAt(i)] = true;
}
public static void main
(String[] args
) { boolean matches;
Test test = new Test();
long start;
System.
out.
println("Regex\n========================="); start
= System.
currentTimeMillis(); // best case
for (int i = 0; i < 100000; ++i)
if (test.matches1("egijlruvw0678"))
System.
out.
printf("Time 1: %d\n",
(System.
currentTimeMillis() - start
)); start
= System.
currentTimeMillis();
// worst case
for (int i = 0; i < 1000000; ++i)
if (!test.matches1("st32pomnbqf51kczyx9"))
System.
out.
printf("Time 2: %d\n",
(System.
currentTimeMillis() - start
)); start
= System.
currentTimeMillis();
// average case
for (int i = 0; i < 1000000; ++i)
if (!test.matches1("st32pomnbq2"))
System.
out.
printf("Time 3: %d\n",
(System.
currentTimeMillis() - start
));
System.
out.
println("Lookup table\n========================="); start
= System.
currentTimeMillis(); // best case
for (int i = 0; i < 100000; ++i)
if (test.matches2("egijlruvw0678"))
System.
out.
printf("Time 1: %d\n",
(System.
currentTimeMillis() - start
)); start
= System.
currentTimeMillis();
// worst case
for (int i = 0; i < 1000000; ++i)
if (!test.matches2("st32pomnbqf51kczyx9"))
System.
out.
printf("Time 2: %d\n",
(System.
currentTimeMillis() - start
)); start
= System.
currentTimeMillis();
// average case
for (int i = 0; i < 1000000; ++i)
if (!test.matches2("st32pomnbq2"))
System.
out.
printf("Time 3: %d\n",
(System.
currentTimeMillis() - start
)); }
}
aW1wb3J0IGphdmEudXRpbC5yZWdleC5QYXR0ZXJuOwoKY2xhc3MgVGVzdCB7CiAgcHJpdmF0ZSBQYXR0ZXJuIHBhdHRlcm47CiAgcHJpdmF0ZSBib29sZWFuW10gdGFibGU7CgogIHB1YmxpYyBib29sZWFuIG1hdGNoZXMxKFN0cmluZyBhKSB7CiAgICByZXR1cm4gcGF0dGVybi5tYXRjaGVyKGEpLm1hdGNoZXMoKTsKICB9CgogIHB1YmxpYyBib29sZWFuIG1hdGNoZXMyKFN0cmluZyBhKSB7CiAgICBpbnQgbGVuZ3RoID0gYS5sZW5ndGgoKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbGVuZ3RoOyArK2kpCiAgICAgIGlmICghdGhpcy50YWJsZVthLmNoYXJBdChpKV0pIHJldHVybiBmYWxzZTsKICAgIHJldHVybiB0cnVlOwogIH0KCiAgcHVibGljIFRlc3QoKSB7CiAgICBTdHJpbmcgY2hhcnMgPSAiYWRoc3QzMnBvbW5icWY1MWtjenl4OTQiOwogICAgdGhpcy5wYXR0ZXJuID0gUGF0dGVybi5jb21waWxlKFN0cmluZy5mb3JtYXQoIlslc10qIiwgY2hhcnMpKTsKICAgIHRoaXMudGFibGUgPSBuZXcgYm9vbGVhblsyNTZdOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBjaGFycy5sZW5ndGgoKTsgKytpKQogICAgICB0aGlzLnRhYmxlW2NoYXJzLmNoYXJBdChpKV0gPSB0cnVlOwogIH0KCiAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgYm9vbGVhbiBtYXRjaGVzOwogICAgVGVzdCB0ZXN0ID0gbmV3IFRlc3QoKTsKCiAgICBsb25nIHN0YXJ0OwoKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiUmVnZXhcbj09PT09PT09PT09PT09PT09PT09PT09PT0iKTsKICAgIHN0YXJ0ID0gU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCk7CiAgICAvLyBiZXN0IGNhc2UKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwMDAwOyArK2kpCiAgICAgIGlmICh0ZXN0Lm1hdGNoZXMxKCJlZ2lqbHJ1dncwNjc4IikpCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJlcnJvciEiKTsKCiAgICBTeXN0ZW0ub3V0LnByaW50ZigiVGltZSAxOiAlZFxuIiwgKFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpIC0gc3RhcnQpKTsKICAgIHN0YXJ0ID0gU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCk7CgogICAgLy8gd29yc3QgY2FzZQogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDAwMDAwOyArK2kpCiAgICAgIGlmICghdGVzdC5tYXRjaGVzMSgic3QzMnBvbW5icWY1MWtjenl4OSIpKQogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiZXJyb3IhIik7CgogICAgU3lzdGVtLm91dC5wcmludGYoIlRpbWUgMjogJWRcbiIsIChTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKSAtIHN0YXJ0KSk7CiAgICBzdGFydCA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwoKICAgIC8vIGF2ZXJhZ2UgY2FzZQogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDAwMDAwOyArK2kpCiAgICAgIGlmICghdGVzdC5tYXRjaGVzMSgic3QzMnBvbW5icTIiKSkKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oImVycm9yISIpOwoKICAgIFN5c3RlbS5vdXQucHJpbnRmKCJUaW1lIDM6ICVkXG4iLCAoU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCkgLSBzdGFydCkpOwoKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTG9va3VwIHRhYmxlXG49PT09PT09PT09PT09PT09PT09PT09PT09Iik7CiAgICBzdGFydCA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwogICAgLy8gYmVzdCBjYXNlCiAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwMDAwMDsgKytpKQogICAgICBpZiAodGVzdC5tYXRjaGVzMigiZWdpamxydXZ3MDY3OCIpKQogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiZXJyb3IhIik7CgogICAgU3lzdGVtLm91dC5wcmludGYoIlRpbWUgMTogJWRcbiIsIChTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKSAtIHN0YXJ0KSk7CiAgICBzdGFydCA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwoKICAgIC8vIHdvcnN0IGNhc2UKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwMDAwMDsgKytpKQogICAgICBpZiAoIXRlc3QubWF0Y2hlczIoInN0MzJwb21uYnFmNTFrY3p5eDkiKSkKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oImVycm9yISIpOwoKICAgIFN5c3RlbS5vdXQucHJpbnRmKCJUaW1lIDI6ICVkXG4iLCAoU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCkgLSBzdGFydCkpOwogICAgc3RhcnQgPSBTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKTsKCiAgICAvLyBhdmVyYWdlIGNhc2UKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwMDAwMDsgKytpKQogICAgICBpZiAoIXRlc3QubWF0Y2hlczIoInN0MzJwb21uYnEyIikpCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJlcnJvciEiKTsKCiAgICBTeXN0ZW0ub3V0LnByaW50ZigiVGltZSAzOiAlZFxuIiwgKFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpIC0gc3RhcnQpKTsKICB9Cn0K