Pagini recente » Cod sursa (job #475816) | Cod sursa (job #2156967) | Cod sursa (job #1417315) | Cod sursa (job #2369339) | Cod sursa (job #2328688)
#include <iostream>
#include <cstdio>
using namespace std;
void gcd(int a, int b){
int t;
while(b){
t=b;
b=a%b;
a=t;
}
cout << a << '\n';
}
#include <bits/stdc++.h>
using namespace std;
string txt, pat;
int z;
vector <int> plm;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base::sync_with_stdio(false);
cin >> pat >> txt;
int M = pat.size();
int N = txt.size();
int lps[M];
//calculam lps
int len = 0;
lps[0]=0; // nu pot fi litere repetate pe prima poz
int i = 1;
while(i<M)
{
if(pat[i]==pat[len])
{
//daca avem 2 elm la fel
++len;
lps[i]=len;
//ne intoarncem direct la len
++i;
}
else
{
if(len!=0)
{
len = lps[len-1];
}
else
{
lps[i] = 0;
++i;
}
}
}
//cautare
int _i = 0; //index pentru txt
int _j = 0; // index pentru pat
while(_i<N)
{
if(pat[_j]==txt[_i])
{
++_i;
++_j;
}
if(_j==M)
{
++z;
if(z<=1000)
plm.push_back(_i-_j);
_j = lps[_j-1]; // ne intoarcem
}
//daca nu a fost gasit
else if(_i<N && pat[_j]!=txt[_i])
{
if(_j!=0)
_j=lps[_j-1];
else ++_i;
}
}
cout << z << '\n';
for_each(plm.begin(),plm.end(),[](int a){
cout << a << ' ';
});
return 0;
}