Cod sursa(job #2738933)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 6 aprilie 2021 16:09:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
    ios::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    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';
    int val = sol.size();
    for(int i = 0; i < min(val,1000); i ++)
        fout << sol[i] << ' ';
}