Cod sursa(job #2679577)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 30 noiembrie 2020 20:42:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 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 ans;

int main()
{
    f >> a >> b;
    int m = strlen(a);
    int n = strlen(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<n) {
        if (b[i]==a[j]) {
            i++;
            j++;
        }
        if (j==m) {
            ans++;
            if (ans<=1000) {
                v.push_back(i-j);
            }
            j = table[j-1];
        }
        else if (i < n && b[i]!=a[j]) {
            if (j!=0) {
                j = table[j-1];
            }
            else {
                i++;
            }
        }
    }
    g << ans <<'\n';
    for (int o=0;o<v.size();o++) {
        g << v[o] << " ";
    }
    return 0;
}