KMPËã·¨µÄJavaʵÏÖÀý×ÓÒÔ¼°²âÊÔ·ÖÎö
±³¾°¼ò½é£ºKMPËã·¨ÓÃÀ´´¦Àí×Ö·û´®Æ¥ÅäµÄ¡£¸øÄãA,BÁ½¸ö×Ö·û´®£¬¼ì²éB´®ÊÇ·ñÊÇA´®µÄ×Ó´®£¬ÀàËÆÓÚJavaµÄString.indexOf("")¡£Ö®ËùÒÔ½Ð×öKMP£¬ÊÇÒòΪÕâ¸öËã·¨ÊÇÓÉKnuth¡¢Morris¡¢PrattÈý¸öÌá³öÀ´µÄ£¬È¡ÁËÕâÈý¸öÈ˵ÄÃû×ÖµÄÍ·Ò»¸ö×Öĸ¡£
ÔÀí½éÉÜ£ºÕÒµ½Æ¥Åäʧ°ÜʱµÄ×îºÏÊʵĻØÍËλÖ㬶ø²»ÊǼòµ¥µÄ»ØÍ˵½×Ó´®µÄµÚÒ»¸ö×Ö·û£¨³£¹æµÄö¾Ù²éÕÒ·½Ê½£¬ÊǼòµ¥µÄ»ØÍ˵½×Ó´®µÄµÚÒ»¸ö×Ö·û£¬½ÓÏÂÀ´×¼±¸Ð´Ò»ÆªKMPËã·¨µÄÐÔÄÜ·ÖÎöJavaʵÏÖʵÀý£©£¬¼´¿ÉÌá¸ß²éÕÒµÄЧÂÊ¡£Òò´ËΪÁËÕÒµ½Õâ¸öºÏÊʵÄλÖã¬ÏȶÔ×Ó´®Ô¤´¦Àí£¬´Ó¶øµÃµ½Ò»¸ö»ØÍËλÖõÄÊý×é¡£¹ý¶àµÄÀíÂ۾Ͳ»½éÉÜÁË¡£
×ÜÌå¶øÑԱȽϼòµ¥£¬KMPËãÒ»¸ö¾µäµÄËã·¨Àý×Ó£¬ºÜ¶à±ÊÊÔ¡¢ÃæÊÔÒ²»áÎÊÆð¡£ÏÖ×ܽáһϣ¬·ÅÔÚÕâÀ﹩´ó¼Ò²Î¿¼¡¢½»Á÷£¬Ï£Íû¶Ô´ó¼ÒÓÐËù°ïÖú£¬ÏÂÃæÖ±½Ó¸ø³öʵÏÖÀý×Ó£¬²âÊÔÓë·ÖÎöÒ²°üº¬ÆäÖС£
Ò»¡¢Ò»¸öÎļþÔ´´úÂë
KMP.java
Ô´´úÂëΪ£º
package algorithm.kmp;
/**
* KMPËã·¨µÄJavaʵÏÖÀý×ÓÓë²âÊÔ¡¢·ÖÎö
* @author ´ÞÎÀ±ø
* @date 2009-3-25
*/
public class KMP {
/**
* ¶Ô×Ó´®¼ÓÒÔÔ¤´¦Àí£¬´Ó¶øÕÒµ½Æ¥Åäʧ°Üʱ×Ó´®»ØÍ˵ÄλÖÃ
* ÕÒµ½Æ¥Åäʧ°ÜʱµÄ×îºÏÊʵĻØÍËλÖ㬶ø²»ÊÇ»ØÍ˵½×Ó´®µÄµÚÒ»¸ö×Ö·û£¬¼´¿ÉÌá¸ß²éÕÒµÄЧÂÊ
* Òò´ËΪÁËÕÒµ½Õâ¸öºÏÊʵÄλÖã¬ÏȶÔ×Ó´®Ô¤´¦Àí£¬´Ó¶øµÃµ½Ò»¸ö»ØÍËλÖõÄÊý×é
* @param B£¬´ý²éÕÒ×Ó´®µÄcharÊý×é
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//ÿѻ·Ò»´Î£¬¾Í»áÕÒµ½Ò»¸ö»ØÍËλÖÃ
for(int i=1;i<size;i++){
//µ±ÕÒµ½µÚÒ»¸öÆ¥ÅäµÄ×Ö·ûʱ£¬¼´j>0ʱ²Å»áÖ´ÐÐÕâ¸öÑ»·
//»òÕß˵p2ÖеÄj++»áÔÚp1֮ǰִÐУ¨ÏÞÓÚµÚÒ»´ÎÖ´ÐеÄÌõ¼þÏ£©
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2£¬ÓÉ´Ë¿ÉÒÔ¿´³ö£¬Ö»Óе±×Ó´®Öк¬ÓÐÖØ¸´×Ö·ûʱ£¬»ØÍ˵ÄλÖòŻᱻÓÅ»¯
if(B[j]==B[i]){
j++;
}
//ÕÒµ½Ò»¸ö»ØÍËλÖÃj£¬°ÑÆä·ÅÈëP[i]ÖÐ
P[i]=j;
}
return P;
&n
Ïà¹ØÎĵµ£º
ÔÚJavaÖУ¬synchronized¹Ø¼ü×ÖΪ·ÀÖ¹×ÊÔ´³åÍ»ÌṩÁËÖ§³Ö£¬Æä×÷ÓÃÓòÓжþÖÖ£º
ʵÀý·¶Î§¡£
¶ÔÏóʵÀý·¶Î§ÄÚsynchronizedʹÓõÄÁ½ÖÖÐÎʽ£º
ʵÀý·¶Î§Í¬²½·½·¨
publicd class syncTest {
…
synchronized void aMethod() {
//ÐèҪͬ²½Ê¹ÓõĴúÂë
}
}
synchronized aMethod(){}¿ÉÒÔ·ÀÖ¹¶à¸öÏß³Ìͬʱ ......
¹Ø¼ü×Ö: java.e800.com.cn/articles/2007/413/1176400876794405339_1.htm
http://java.e800.com.cn/articles/2007/413/1176400876794405339_1.html
±àÕß°´£ºJavaÄÚ´æÐ¹Â©ÊÇÿ¸öJava³ÌÐòÔ±¶¼»áÓöµ½µÄÎÊÌ⣬³ÌÐòÔÚ±¾µØÔËÐÐÒ»ÇÐÕý³££¬¿ÉÊDz¼Êðµ½Ô¶¶Ë¾Í»á³öÏÖÄÚ´æÎÞÏÞÖÆµÄÔö³¤£¬×îºóϵͳ̱»¾£¬ÄÇôÈçºÎ×î¿ì×îºÃµÄ¼ì²â³ÌÐòµÄÎ ......
game
server responsibility:
Initialize
the server socke;
Wait
for a client to connect;
Accept
the client connection;
Create
a daemon thread to support the clien;
Go
back to step 2.
game daemon responsibility:
Accept
client player connection;
Pair
......