Cod sursa(job #3196436)

Utilizator Ionut2212Nedelcu Alexandru Ionut Ionut2212 Data 23 ianuarie 2024 21:22:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[2000001], s2[2000001]; short v[2000001];
int v2[100000];
int main()
{
    int n, m, z = 0;
    v[0] = 0;
    fin.get(s,2000000);
    fin.get();
    fin.get(s2,2000000);
    //cout << s;
    //cout << s2;
    n = strlen(s2);
    m = strlen(s);
    for(int i = 1; i < m; i++)
    {
        if(v[i-1] != 0)
        {
            if(s[v[i-1]] == s[i])
            {
                v[i] = v[i-1] + 1;
            }
            else v[i] = 0;
        }
        else
        {

            if(s[i] == s[0]) v[i] = 1;

            else v[i] = 0;
            //cout << s[i] << ' ' << s[0] << v[i];
        }
    }
    int i = 0;
    int j = 0;

    while(i < n)
    {
        if(s[j] == s2[i])
        {
            i++;
            j++;
        }
        if(j == m)
        {
            v2[++z] = i - m;
            j = v[j-1];
        }
        else if(i < n && s[j] != s2[i])
        {
            if(j != 0)
            {
                j = v[j-1];
            }
            else i++;
        }
    }
    fout << z << endl;
    for(int i = 1; i <= z; i++)
        fout << v2[i] << ' ';
    /*
    for(int i = 0; i < m; i++)
    {
        cout << v[i];
    }*/
    return 0;
}