Cod sursa(job #2691997)

Utilizator Iustin01Isciuc Iustin - Constantin Iustin01 Data 30 decembrie 2020 23:54:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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, sol[1005];

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++;
        if(k == n && cnt < 1000){
            sol[++cnt] = i - n;
        }
    }

    out<<cnt<<"\n";
    for(int i = 1; i <= cnt; i++)
        out<<sol[i]<<" ";

}