Cod sursa(job #2061536)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 9 noiembrie 2017 13:48:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#include <ctime>
#include <stdlib.h>
#define MAX 500000000000
//#include <iostream>
//#include <windows.h>
#include <deque>
//#include "PEZai.h"
//#include <Tlhelp32.h>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
//ifstream cin("indep.in");
//ofstream cout("indep.out");
int z[4000005], sols[4000003];
char v[4000003], rep[4000003];
string s;
int n;
void comparison(int val, int l, int r, int index, string s)
{
    int k = index + 1;
    for(int i = index - l + 1; i < index; i++)
    {
        if(k + z[i] >= r)
        {
            int ll = i + 1, rr = k + 1, v = 0;
            while(s[ll] == s[rr])
            {
                ll++;
                rr++;
                v++;
            }
            val += v;
        }
    }
}
void computeZfunction(int z[], string s)
{
    int l, r, n = s.size(), index = 1, ok = 0;
    for(int i = 1; i < n; i++)
    {
        if(ok == 0)
            l = 0, r = i;
        while(s[l] == s[r])
        {
            r++;
            l++;
        }
        z[i] += l;
        r += l;
        comparison(z[i], l, r, i, s);
    }
}
int main()
{
    //cin >> s;
    int k = 0;
    char a;
    cin.get(v, 2000004);
    int n = strlen(v);
    for(int i = 0; i < n; i++)
        rep[i] = v[i];
    rep[n] = '&';
    cin.get();
    cin.get(v, 2000004);
    int c = strlen(v);
    for(int i = 0; i < c; i++)
        rep[n + i + 1] = v[i];
    s = rep;
    computeZfunction(z, s);
    for(int i = 0; i < s.size(); i++)
        if(z[i] == n){
            sols[k++] = i;
        }
    cout << k << "\n";
    for(int i = 0; i < k; i++)
        cout << sols[i] - n - 1 << " ";
}