Cod sursa(job #2447395)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 13 august 2019 11:38:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
#define maxim 2000003

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
int dp[maxim];


int main()
{
    string a, b;
    f >> a >> b;
    int len = a.size();
    a += '*';
    a+= b;
    vector <int> id;
    int ans = 0;
    dp[0] = -1;
    for (int i = 1; i < a.size(); ++ i)
    {
       int j = i - 1;
       while (dp[j] != -1 && a[i] != a[dp[j] + 1])
           j = dp[j];

       dp[i] = dp[j];
       if (a[i] == a[dp[j] + 1])
           dp[i] = dp[j] + 1;

       if (dp[i] + 1 == len)
       {
           ans ++;
           if (ans <= 1000)
           id.push_back(i - 2 * len);
       }
    }
    g << ans <<'\n';
    for (auto i : id)
        g << i << " ";

}