Cod sursa(job #2191229)

Utilizator NashikAndrei Feodorov Nashik Data 2 aprilie 2018 10:51:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 8.33 kb
#include <cstdio>
#include <cstring>
#include <fstream>
using namespace std;
long long cod(char c)
{
    if(c>='A' and c<='Z')
        return c - 'A';
    if(c>='0' and c<='9'){
        return c-'0'+'Z'+1;
    }
    return c-'a'+'Z'+'9'+2;
}

const long long BASE = 79;
const long long MOD = 100000007;

long long powBase[2000005];

long long hashPref[2000005];
char T[2000005];
char P[2000005];

long long cod(char* s)
{
    long long answer = 0;
    while (s[0] != '\0')
    {
        answer = (answer * BASE + cod(s[0])) % MOD;
        s++; // ca si cand am 'sterge' primul caracter
    }
    return answer;
}


long long hashh(long long i, long long j)
{
    return (hashPref[j] + MOD - hashPref[i - 1] * powBase[j - (i - 1)] % MOD) % MOD;
}

//   i j
//abcdefghi
//abcdef
//abc---
int v[2000005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",P,T);
    long long lenT=strlen(T);
    long long lenP=strlen(P);
    powBase[0]=1;
    for(long long i=1;i<=2000005;i++)
        powBase[i]=powBase[i-1]*BASE%MOD;
    hashPref[0]=(cod(T[0])+MOD)%MOD;
    for(long long i=1;i<lenT;i++)
        hashPref[i]=(hashPref[i-1]*BASE+cod(T[i]))%MOD;
    long long Phash=cod(P);
    long long cnt=0;
    for(long long i=0;i+lenP<=lenT;i++)
        if(Phash==hashh(i,i+lenP-1)){
            v[++cnt]=i;
        }
    printf("%d\n",cnt);
    cnt=min(cnt,(long long)(1000));
    for(int i=1;i<=cnt;i++){
        printf("%d ",v[i]);
    }
    return 0;
}
//1264
//2910 2936 2962 5817 9884 9910 16997 17023 20699 20725 20751 22919 22945 22971 29694 29720 29746 29772 35691 35717 35743 39444 42897 42923 46347 48460 48486 50896 55110 55136 55162 61241 64352 69178 72012 72038 74558 77267 77293 77319 80595 82782 86568 86594 89129 93568 96781 99206 99232 103663 103689 103715 108031 108057 108083 110277 116835 119331 119357 125724 125750 125776 125802 128601 132572 132598 132624 135541 135567 138014 144432 147176 150186 150212 150238 152918 152944 152970 158886 158912 158938 164352 168433 168459 173546 173572 173598 173624 173650 173676 173702 173728 173754 173780 173806 173832 173858 173884 173910 173936 173962 173988 174014 174040 174066 174092 174118 174144 174170 174196 174222 174248 174274 174300 174326 174352 174378 174404 174430 174456 174482 174508 174534 174560 174586 174612 174638 174664 174690 174716 174742 174768 174794 174820 174846 174872 174898 174924 174950 174976 175002 175028 175054 175080 175106 175132 175158 175184 175210 175236 175262 175288 178257 178283 182155 182181 182207 185170 190657 193023 193049 195308 197507 197533 197559 197585 197611 197637 197663 197689 197715 197741 197767 197793 197819 197845 197871 197897 197923 197949 200078 200104 200130 200156 200182 200208 200234 200260 200286 200312 200338 200364 200390 200416 200442 200468 200494 200520 200546 200572 200598 200624 200650 200676 200702 200728 200754 200780 207361 207387 207413 211132 213708 213734 213760 217432 220462 220488 220514 224636 224662 226786 226812 226838 234179 239239 239265 239291 241985 244386 244412 244438 244464 244490 244516 244542 244568 244594 244620 244646 244672 244698 248318 248344 252452 259743 259769 259795 264840 264866 264892 268822 268848 271662 275301 280212 280238 280264 280290 283482 286634 286660 286686 286712 286738 286764 286790 286816 286842 286868 286894 286920 286946 286972 286998 287024 287050 287076 287102 287128 287154 287180 287206 287232 287258 287284 287310 287336 287362 287388 287414 287440 287466 287492 287518 287544 287570 287596 287622 287648 287674 287700 287726 287752 287778 287804 287830 287856 287882 287908 287934 287960 287986 288012 288038 288064 288090 294180 301344 301370 306272 308501 308527 308553 308579 311137 314142 317767 321145 326151 332827 332853 332879 332905 332931 332957 332983 333009 333035 333061 333087 333113 335722 338986 339012 339038 341820 341846 341872 347754 352500 352526 356359 356385 356411 359973 359999 367850 372792 376691 382069 382095 387637 389748 393907 393933 393959 396088 396114 396140 404262 407549 407575 407601 412153 415210 415236 415262 420560 425645 428392 428418 431922 431948 435474 435500 438490 441363 447607 450507 450533 450559 450585 450611 450637 450663 450689 450715 450741 450767 450793 450819 450845 450871 450897 450923 450949 450975 451001 451027 451053 457637 457663 457689 460857 460883 460909 460935 464466 467108 467134 467160 470000 470026 470052 472423 472449 472475 472501 472527 472553 472579 472605 472631 472657 472683 472709 472735 472761 472787 472813 472839 472865 472891 472917 472943 472969 472995 473021 473047 473073 473099 473125 473151 473177 473203 473229 473255 473281 473307 473333 473359 473385 473411 473437 473463 473489 473515 473541 473567 473593 473619 473645 473671 473697 473723 473749 473775 473801 473827 473853 473879 473905 473931 473957 473983 474009 478137 478163 478189 484208 484234 484260 490115 496392 496418 499615 504507 504533 504559 507430 511695 517537 517563 521106 523915 523941 523967 526770 526796 529090 529116 532129 535053 535079 535105 535131 535157 535183 535209 535235 535261 535287 535313 535339 535365 535391 535417 535443 535469 535495 535521 535547 535573 535599 535625 535651 535677 535703 535729 535755 535781 535807 535833 535859 535885 535911 535937 535963 535989 536015 536041 536067 536093 539239 539265 541377 544150 544176 547596 547622 551443 557202 559799 563273 563299 563325 563351 563377 563403 563429 563455 563481 563507 563533 563559 563585 563611 563637 563663 563689 563715 563741 563767 563793 563819 563845 563871 563897 563923 563949 563975 564001 564027 564053 564079 564105 564131 564157 564183 564209 564235 564261 564287 564313 564339 564365 564391 564417 564443 564469 564495 564521 564547 566936 566962 571274 574500 578123 582063 584893 584919 584945 587923 591611 591637 591663 591689 591715 591741 591767 591793 591819 591845 591871 591897 591923 591949 591975 592001 592027 592053 592079 592105 592131 592157 592183 592209 592235 592261 592287 592313 592339 592365 592391 592417 592443 594550 596834 599726 599752 599778 599804 603035 603061 607564 607590 611507 614423 619090 619116 619142 624583 624609 624635 628223 628249 628275 630473 630499 635544 639775 644671 644697 644723 646844 646870 646896 646922 646948 646974 647000 647026 647052 647078 647104 647130 647156 647182 647208 647234 647260 647286 647312 647338 647364 647390 647416 647442 647468 647494 647520 647546 647572 647598 647624 647650 650908 650934 653509 653535 656411 656437 658724 658750 662453 666464 666490 669927 674657 679099 679125 683056 683082 687912 687938 691787 691813 691839 698150 698176 698202 698228 704173 704199 704225 707593 712825 723352 723378 723404 727563 727589 730181 730207 730233 736830 739454 739480 739506 739532 739558 739584 739610 739636 739662 739688 739714 739740 739766 739792 739818 739844 739870 739896 739922 739948 739974 740000 740026 740052 740078 740104 740130 740156 740182 740208 740234 740260 740286 740312 740338 740364 740390 740416 740442 740468 740494 740520 740546 740572 743903 743929 743955 746344 746370 746396 749064 749090 754017 754043 754069 754095 757008 757034 757060 757086 757112 757138 757164 757190 757216 757242 757268 757294 757320 762881 762907 768909 771181 773298 773324 773350 773376 773402 773428 773454 773480 773506 773532 773558 773584 773610 773636 775759 778669 782820 789839 789865 793777 793803 793829 793855 793881 793907 793933 793959 793985 794011 794037 794063 794089 794115 794141 794167 794193 794219 794245 794271 794297 794323 794349 794375 798265 805121 807242 807268 807294 807320 807346 807372 807398 807424 807450 807476 807502 807528 807554 807580 807606 807632 807658 807684 807710 807736 807762 807788 807814 807840 807866 807892 807918 807944 807970 807996 808022 808048 808074 808100 808126 808152 808178 808204 813813 819813 819839 819865 824361 824387 824413 828228 828254 828280 830948 837129 843924 846050 846076 846102 849301 852771 857007 857033 857059 861251 861277 861303 864460 869290 869316 869342 874260 874286 878874 881934 886312 889015 889041 889067 893363 893389 896400 901465 901491 903795 906053 909509 909535 909561 915033 919038 919064 923357 923383 923409 925598 925624 927748 927774 927800 927826 927852 927878 927904 927930 927956 927982 928008 928034 928060 928086 928112 928138 928164 928190 928216 928242 931050 931076 933391 937850 943552 948631 956298 956324 959465 962406 962432 962458 968178