Cod sursa(job #3253030)

Utilizator GabiRB1Rafael GabiRB1 Data 31 octombrie 2024 22:18:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
char s[2000005], w[2000005];
int n, m, ps[2000005], pw[2000005];
vector <int> v;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f >> s;
    f >> w;
    n = strlen(s), m = strlen(w);
    for(int i = 1; i < n; i ++)
    {
        int j = ps[i - 1];
        while(j > 0 && s[i] != s[j])
            j = ps[j - 1];
        if(s[i] == s[j])
            j ++;
        ps[i] = j;
    }
    int j = 0;
    for(int i = 0; i < m; i ++)
        {
            while(j > 0 && s[j] != w[i])
                j = ps[j - 1];
            if(s[j] == w[i])
                j ++;
            if(j == n)
            {
                j = ps[n - 1];
                if(v.size() < 1000)
                    v.push_back(i - n + 1);
            }
        }
    g << v.size() << "\n";
    for(int i = 0; i < v.size(); i ++)
        g << v[i] << " ";
    return 0;
}