Cod sursa(job #2278363)

Utilizator tigeraOprea Tereza Emilia tigera Data 7 noiembrie 2018 18:25:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
//
//  main.cpp
//  potrivirea_sirurilor
//
//  Created by Tereza Oprea on 07/11/2018.
//  Copyright © 2018 Tereza Oprea. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

char pattern[2000010], text[2000010];

int d[2000010], t[2000010], i, j;
unsigned long n1, n2;
int ans, v[20000010];

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

int main() {
    fin.getline(pattern, 2000010);
    fin.getline(text, 2000010);
    i = 0; j = 1;
    n1 = strlen (pattern);
    n2 = strlen (text);
    while (j<n1){
        if ( pattern[i] == pattern[j]){
            d[j] = i+1;
            i++;
            j++;
            continue;
        }
        if ( i == 0 ){
            j++;
            continue;
        }
        i = d[i-1];
    }
    i = 0; j = 0;
    int lun = 0;
    while (j < n2){
        if (pattern[i] == text[j]){
            lun++;
            if (lun == n1){
                ans++;
                v[ans] = j - n1 + 1;
                i = d[n1-1];
                lun = i;
                j++;
                continue;
            }
            i++;
            j++;
            continue;
        }
        if (i == 0){
            lun = 0;
            j++;
            continue;
        }
        i = d[i-1];
        lun = i;
    }
    fout << ans << '\n';
    for (i = 1; i<=ans; i++)
        fout << v[i] << ' ';
    return 0;
}