Cod sursa(job #2518433)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 5 ianuarie 2020 18:28:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<bits/stdc++.h>
#define LungMax 2000005
using namespace std;
int i, j, sufix[LungMax], n, m, ans[1005], k;
char s[LungMax], t[LungMax];
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(t, sizeof(t));
    f.getline(s, sizeof(s));
    n = strlen(s);
    m = strlen(t);
    j = 0;
    i = 1;
    while(i < m)
    {
        if(t[j] == t[i])
        {
            sufix[i] = j + 1;
            j ++;
            i ++;
        }
        else if(j == 0)sufix[i] = 0, i ++;
            else j = sufix[j - 1];

    }
    j = 0;
    for(i = 0; i < n; i ++)
        if(s[i] == t[j])
        {
            j ++;
            if(j == m && k <= 1001)ans[++ k] = i - m + 1, j = sufix[j - 1];
        }
        else if(j == 0)continue;
        else j = sufix[j - 1], i --;
    g << k << "\n";
    for(i = 1; i <= min(k, 1001); i ++)
        g << ans[i] << " ";
	return 0;
}