Cod sursa(job #2530736)

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

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

int n, m,cnt, pi[MAX] , z, v[1001];
char s1[MAX], s2[MAX];

int main(){
    in.getline(s1, MAX);
    in.getline(s2, MAX);
    n = strlen(s1);
    m = strlen(s2);
    for(int i = n; i >= 1; i--)
        s1[i] = s1[i-1];
    for(int j = m; j >= 1; j--)
        s2[j] = s2[j - 1];
    s1[0] = s2[0] = ' ';

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

        pi[i] = k;
    }
    k = 0;
    for(int i = 1; i <= m; i++){
        while(k > 0 && s1[k+1] != s2[i])
            k = pi[k];
        if(s1[k + 1] == s2[i])
            k++;
        if(k == n && z <= 1000) v[++z] = i - n;
    }
    out<<z<<"\n";
    for(int i = 1; i <= z; i++)
        out<<v[i]<<" ";
}