Cod sursa(job #2721178)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 11 martie 2021 16:58:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

char v[2000002];
char w[2000002];
int pi[2000002], ans;
vector<int> sol;

int main()
{
    fin >> (v+1);
    fin >> (w+1);
    int n = strlen(v+1);
    int m = strlen(w+1);
    int j = 0;
    for(int i = 2; i <= n; i ++)
    {
        while(v[i] != v[j+1] && j != 0)
        {
            j = pi[j];
        }
        if(v[i] == v[j+1])
        {
            j++;
        }
        pi[i] = j;
    }
    j = 0;
    for(int i = 1; i <= m; i ++)
    {
        while(w[i] != v[j + 1] && j != 0)
        {
            j = pi[j];
        }
        if(w[i] == v[j + 1])
            j++;
        if(j == n)
        {
            ans++;
            sol.push_back(i-j);
        }
    }
    fout << ans << '\n';
    for(int i = 0; i < min(1000,ans); i ++)
        fout << sol[i] << ' ';
    return 0;
}