Pagini recente » Cod sursa (job #137670) | Cod sursa (job #2239522) | Cod sursa (job #2700155) | Cod sursa (job #2163343) | Cod sursa (job #1673207)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000007;
int N, M, pi[MAXN];
vector<int>match;
char A[MAXN], B[MAXN];
void makepi()
{
pi[1] = 0;
for(int i = 2, q = 0; i <= N; ++i)
{
while(q && A[q + 1] != A[i])
q = pi[q];
if(A[q + 1] == A[i]) ++q;
pi[i] = q;
}
}
void find_matches()
{
int q(0);
for(int i = 1; i <= M; ++i)
{
while(q && A[q + 1] != B[i])
q = pi[q];
if(A[q + 1] == B[i]) ++q;
if(q == N)
{
if(match.size() + 1 <= 1000)
match.push_back(i - N + 1);
q = pi[q];
}
}
}
void print(ofstream &cout)
{
cout << match.size() << '\n';
for(auto itr : match)
cout << itr - 1 << ' ';
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> (A + 1) >> (B + 1);
N = strlen(A + 1), M = strlen(B + 1);
makepi();
find_matches();
print(cout);
return 0;
}