Pagini recente » Cod sursa (job #3223320) | Cod sursa (job #753730) | Cod sursa (job #3221754) | Cod sursa (job #33410) | Cod sursa (job #2709298)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <climits>
#include <queue>
#define MOD 666013
using namespace std;
ifstream cin("strmatch.in") ;
ofstream cout("strmatch.out") ;
/// string matching folosind strstr(), nu kmp sau alte vrajeli
/// pt majoritatea cazurilor putem face pur si simplu strstr si apoi mergem de la elem urm indicat de pointer si cautam urm aparitie, pe infoarena asta ia vreo 96 pct daca nar avea ei sistemul ala retard
/// pt eficienta identica cu kmp este necesara o optimizare foarte complicata care nu se merita de obicei :
/// se afla cat de mult se suprapune stringul de cautat cu el insusi, de ex daca il gasim pe aabaaa in b atunci mai trebuie doar sa cautam daca exista un baaa dupa aabaaa -ul gasit, si daca se tot intampla sa existe
/// continuam asa, deci nu trecem niciodata de doua ori prin aceleasi char-uri, in rest daca nu exista folosim strstr sa gasim urm aparitie a lui a in b
vector<int> v ;
int process(string a) /// determinam indicele pana la care se suprapune a cu el insusi de ex pt stringul casian k = a.size() deci se pot lipi unul in spatele altuia, dar pt aaabaaa k = 4, adica se poate avea :
/// aaabaaabaaa si aici apare aaabaaa de doua ori
{
int k = 0 ;
for(int f = a.size() - 1 ; f >= 0 ; f --)
{
/// dau match la primele f caract si ultimele f caract
string st = a.substr(0, f) ;
string dr = a.substr(a.size() - f, a.size()) ;
if(st == dr)return a.size() - f ;
}
return a.size() ;
}
int main()
{
string a, b ;
cin >> a >> b ;
int k = process(a) ;
string remainder = a.substr(a.size() - k, a.size() - k + a.size() - k) ; /// pe asta il cautam de la capat, daca este prezent acolo atunci continuam altfel doar cautam de la capat tot striungul
char *ptr = &b[0], *auxptr ;
while(auxptr = strstr(ptr, &a[0]))
{
v.push_back(auxptr - &b[0]) ;
/// lam gasit pe a in auxptr
/// acuma trebe sa vedem daca la sfarsitul lui a se afla remainder
int poz = auxptr - &b[0] + a.size() ;
while(remainder.size() && b.substr(poz, remainder.size()) == remainder)
{
poz += remainder.size() ; /// poz devine sfarsitul lui remainder
v.push_back(poz - a.size()) ;
}
ptr = &b[poz - 1] ;
}
cout << v.size() << endl ;
for(int f = 0 ; f < v.size() && f < 1000 ; f ++)
cout << v[f] << " " ;
return 0 ;
}