Cod sursa(job #2321566)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 16 ianuarie 2019 11:44:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
char s[2000005], c[2000005];
int i, j, a[2000005], v[2000005], k, n, m;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(c, sizeof(c));
    f.getline(s, sizeof(s));
    n = strlen(c);
    m = strlen(s);
    i = 1;
    j = 0;
    while(i < n)
    {
        if(c[i] == c[j])
        {
            a[i] = j + 1;
            i++;
            j++;
        }
        else
        {
            if(j == 0)i++;
            else j = a[j - 1];
        }
    }
    i = 0;
    j = 0;
    while(i < m)
    {
        if(s[i] == c[j])
        {
            i++;
            j++;
            if(j == n)v[++k] = i - n;
        }
        else
        {
            if(j == 0)i++;
            else j = a[j - 1];
        }
    }
    g << k << "\n";
    for(i = 1; i <= k; i ++)
        g << v[i] << " ";
    return 0;
}