Cod sursa(job #2198717)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 25 aprilie 2018 10:26:23
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

long long capat, q, k, contor, j, prev2[2000004], i, total, sol[2000004];
char v[2000004], t[2000004];

int main()
{
    cin >> v >> t;
    q = strlen(v);
    for(int i=0; i < q; i++)
    {
        if(v[i] >= 'a' && v[i] <= 'z')
        v[i] = v[i]-'a'+'A';
    }
    q = strlen(t);
    for(int i=0; i < q; i++)
    {
        if(t[i] >= 'a' && t[i] <= 'z')
        t[i] = t[i]-'a'+'A';
    }

    contor = strlen(v);

    for(i=1; i < contor; i++)
    {
        if(i == contor-1)
        {
            i++;
            i--;
        }

        //if(v[j] != v[i] && j > 0)
        //j--;

        while(v[j] != v[i] && j != 0)
        j = prev2[j-1];

        if(v[j] == v[i])
        prev2[i] = j+1;
        else
        prev2[i] = 0;

        j++;
    }
//    for(int i=0; i < contor; i++)
//    cout << prev2[i] << ' ';
//    cout << "\n\n";

    q = strlen(t);
    j = 0;
    for(int i=0; i < q; i++)
    {
        while(t[i] != v[j] && j > 0)
        j = prev2[j-1];
        if(t[i] == v[j])
        j++;
        if(j == contor)
        {
            total++;
            sol[total] = i-contor+1;
        }
    }
    cout << total << '\n';
    if(total <= 1000)
    capat = total;
    else
    capat = 1000;

    for(int i=1; i <= capat; i++)
    cout << sol[i] << ' ';
}