Cod sursa(job #2692586)

Utilizator Iustin01Isciuc Iustin - Constantin Iustin01 Data 3 ianuarie 2021 11:43:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define MAX 2000005
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");


char s1[MAX], s2[MAX];
int pi[MAX], d[MAX];
int i, k, n, m, cnt, x;

void build_pi(){
    for(int i = 2; i <= n; i++){
        while(k && s1[i] != s1[k + 1])
            k = pi[k];
        if(s1[i] == s1[k + 1])
            k++;
        pi[i] = k;
    }
}

int main(){
    in.getline(s1 + 1, MAX);
    in.getline(s2 + 1, MAX);
    s1[0] = s2[0] = ' ';
    n = strlen(s1) - 1;
    m = strlen(s2) - 1;
    build_pi();
    k = 0;
    for(int i = 1; i <= m && cnt < 1000; i++){
        while(k && s2[i] != s1[k + 1])
            k = pi[k];
        if(s2[i] == s1[k + 1])
            k++;
        d[i] = k;
    }

    for(int i = 1; i <= m && cnt < 1000; i++)
        if(d[i] == n)
            x++, cnt++;
    out<<x<<"\n";
    cnt = 0;
    for(int i = 1; i <= m && cnt < 1000; i++)
        if(d[i] == n)
            out<<i - n<<" ", cnt++;

}