Cod sursa(job #2721739)

Utilizator LawrentiuTirisi Claudiu Lawrentiu Data 12 martie 2021 10:36:52
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <string.h>
#include <fstream>
#include <vector>
#include <cstdlib>
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");

char *read()
{
    char *s = NULL;
    int len = 0;
    char c;
    while (f >> noskipws >> c)
    {
        if (c == '\n')
        {
            s[len] = '\0';
            break;
            return s;
        }
        else
        {
            len++;
            s = (char *)realloc(s, len * sizeof(char));
            s[len - 1] = c;
        }
    }
    s[len] = '\0';
    return s;
}

bool check(char *s1, char *s2, int poz)
{
    int len1 = strlen(s1), len2 = strlen(s2);
    int i;
    for (i = poz; i < poz + len1; i++)
        if (s1[i-poz] != s2[i])
            break;
    return i == poz + len1;
}

int main()
{
    char *s1 = read(), *s2 = read();

    int len1 = strlen(s1), len2 = strlen(s2);
    if(len1>len2){
        o<<0;
        return 0;
    }
    vector<int> result;

    // compute the first hash
    int hash1 = 0, hash2 = 0;
    for (int i = 0; i < len1; i++)
    {
        hash1 += s1[i];
        hash2 += s2[i];
    }
    if (hash1 == hash2 && check(s1, s2, 0))
        result.push_back(0);
    for (int i = 1; i < len2 - len1 + 2; i++)
    {
        hash2 = hash2 - s2[i - 1] + s2[i + len1 - 1];
        if (hash1 == hash2){
            if (check(s1, s2, i))
                result.push_back(i);
        }
    }
    o << result.size() << "\n";
    for (vector<int>::iterator i = result.begin(); i != result.end(); ++i)
        o << *i << " ";
}