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µÄÉè¼ÆÄ£Ê½¡£±¾È˵Äˮƽ²»ÊǺܸߣ¬ÕâϵÁÐÎÄÕÂÖ»ÊÇ×Ô¼ºÑ§Ï°µÄ¹ý³Ì£¬²¢Ï£ÍûÄÜͬ´ó¼Ò·ÖÏí¾Ñé¡£
ÏÈ˵ÏÂÎÒ¶Ô¹¤³§Ä£Ê½µÄÀí½â£ºµ±ÎÒÃÇÐèҪij¸ö¶ÔÏóʱ£¬×îÖ±½ÓµÄ°ì·¨ÊÇ¿´µ½Õâ¸ö¶ÔÏó¾ÍÄùýÀ´¡£µ«Êǵ±¶ÔÏó·Ç³£¶àµÄʱºò£¬ÕÒÆðÀ´¾ÍºÜ²»·½±ã¡£Õâʱ¾ÍÐèÒªÒ»¸öÖнéÀ´°ïÖúÎÒÃÇÈ¡µÃÏëÒªµÄ¶«Î÷£¬Õâ¸öÖнé¾ÍÊǹ¤³§£¨fa ......
·½·¨µÄÖØÔØ
£ºÍ¬Ò»¸öÀàÀïÃæ·½·¨µÄÃû×ÖÏàͬ£¬·½·¨µÄ²ÎÊýÏÖ÷ÒªÊDzÎÊýÀàÐÍ£¬²ÎÊý¸öÊý£©
²»Í¬
,
·µ»ØÀàÐÍ¿ÉÄܲ»Í¬¡£
ÖØÔØ·½·¨¿ÉÒÔ¾ßÓв»Í¬µÄ·µ»ØÀàÐÍ£¬µ«·µ»ØÀàÐͱ¾Éí²»×ãÒÔÇø·Ö·½·¨µÄÁ½¸ö°æ
±¾¡£ ......
Ò»¡¢Ê²Ã´ÊÇ·´É䣺
·´ÉäµÄ¸ÅÄîÊÇÓÉSmithÔÚ1982ÄêÊ×´ÎÌá³öµÄ£¬Ö÷ÒªÊÇÖ¸³ÌÐò¿ÉÒÔ·ÃÎÊ¡¢¼ì²âºÍÐÞ¸ÄËü±¾Éí״̬»òÐÐΪµÄÒ»ÖÖÄÜÁ¦¡£ÕâÒ»¸ÅÄîµÄÌá³öºÜ¿ìÒý·¢Á˼ÆËã»ú¿ÆÑ§ÁìÓò¹ØÓÚÓ¦Ó÷´ÉäÐÔµÄÑо¿¡£ËüÊ×Ïȱ»³ÌÐòÓïÑÔµÄÉè¼ÆÁìÓòËù²ÉÓÃ,²¢ÔÚLispºÍÃæÏò¶ÔÏó·½ÃæÈ¡µÃÁ˳ɼ¨¡£ÆäÖÐLEAD/LEAD++ ¡¢OpenC++ ¡¢MetaXaºÍOpenJavaµÈ¾ÍÊÇ»ùÓÚ·´ ......
Javaѧϰ·Ïß
ÏÈѧϰj2se
Ҫѧϰj2ee¾ÍÒªÏÈѧϰj2se£¬¸Õ¿ªÊ¼Ñ§Ï°j2seÏȽ¨Ò鲻ҪʹÓÃIDE£¬È»ºó½¥½¥µÄ¹ý¶Éµ½Ê¹ÓÃIDE¿ª·¢£¬±Ï¾¹ÓÃËü·½±ãÂѧϰj2seÍÆ¼öÁ½±¾Ê飬¡¶java2ºËÐļ¼ÊõÒ»¶þ¾í¡·£¬¡¶java±à³Ì˼Ïë¡·£¬¡¶javaģʽ¡·¡£ÆäÖС¶java±à³Ì˼Ïë¡·ÒªÑжÁ£¬¾«¶Á¡£ÕâÒ»¶Îʱ¼äÊÇ»ù±¾¹¦Ñ§Ï°£¬Ê±¼ä»áºÜ³¤£¬Ò²¿ÉẠ̈ܺܶ¬ÕâÒª¿´Ñ§Ï ......
JavaÖ´ÐÐstm.executeQuery(sql); ʱ×ÜÊÇÌáʾ£ºjava.sql.SQLException: ORA-00911: ÎÞЧ×Ö·û£¬ÅªÁ˰ëÌ컹Êdzö´í£¬ÎÞÄΣ¬ÄóöɱÊÖïµ£¬Googleһϣ¬Ôε¹£¬·¢ÏÖÎÒµÄString sql = “select detail from test.result where person_id = 4; "£¬Ã²ËÆÃ»´íÎó°É£¬½á¹ûÎÒÎÒ±ØÐëÈ¥µô×îºó·ÖºÅ£¬±¾À´ÊÇÏë¸ãµÃרҵµã£¬¾Í¼Û¼Ó¸ö·Ö ......