Cod sursa(job #2679544)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 30 noiembrie 2020 19:23:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;

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

char a[2000005];
char b[2000005];
int table[2000005];
vector < int > v;

int main()
{
    f >> a >> b;
    for (int i=1;i<strlen(a);i++) {
        if (a[i]==a[table[i-1]]) {
            table[i] = table[i-1] +1;
        }
    }
    int i=0,j=0;
    while (i<strlen(b)) {
        if (b[i]==a[j]) {
            i++;
            j++;
            if (j==strlen(a)) {
                v.push_back(i-strlen(a));
            }
        }
        else if (j!=0) {
            j = table[j-1];
        }
        else {
            i++;
        }
    }
    g << v.size() <<'\n';
    for (int o=0;o<v.size();o++) {
        g << v[o] << " ";
    }
    return 0;
}